Method and apparatus for optimizing system operational parameters

• US 4,744,027 A
• Filed: 08/22/1986
• Issued: 05/10/1988
• Est. Priority Date: 08/22/1986
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Inventors: Bayer, David A., Lagarias, Jeffrey C., Karmarkar, Narendra K.
• Primary Examiner(s): Ruggiero, Joseph F.
• Assistant Examiner(s): Meyer, Charles B.
• Application Number:
  US06/899,191
• Time in Patent Office: 627 Days
• Field of Search: 364/402, 379/113, 379/221, 340/827
• US Class Current: 705/7.22
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
• CPC Class Codes: G06Q 10/06314 Calendaring for a resource

Abstract

Method and apparatus for optimizing the operational state of a system employing iterative steps that approximately follow a projective scaling trajectory or an affine scaling trajectory, or curve, in computing from its present state, x₀ to a next state x₁ toward the optimum state. The movement is made in a transformed space where the present (transformed) state of the system is at the center of the space, and the curve approximation is in the form of a power series in the step size. The process thus develops a sequence of tentative states x₁, x₂, x_n . . . . It halts when a selected suitable stopping criterion is satisfied, and assigns the most recent tentative state as the optimized operating state of the system.

Claims

1. Apparatus for optimizing the operating state of a communications network comprising:

a plurality of sensors for developing signals representative of present operating state of said network, said signals being related to controllable parameters of said network;

first processor, responsive to said sensors, for transforming said signals onto a multi-dimensional space such that said operational state of said communications network is at essentially the center of said multi-dimensional space and said constraints form a polytope in said space;

second processor, responsive to said first processor, for computing a path in said space characterized by a power series of order greater than one, along which values of said signals in said space represent a state of said communications network that is monotonically improving with distance from said center; and

third processor, reponsive to said second processor, for selecting a point on said curve, developing a modified set of signals corresponding to said selected point and controlling said parameters of said communication network in accordance with said modified set of signals.

2. Apparatus for optimizing the operational state of a system in accordance with a preselected operational criterion by adjusting values of operational parameters controlling said state of said system, said operational parameters being adjustable within a preselected set of linear constraints, comprising:

a first processor portion for developing signal representations of said operational parameters and for developing, a preselected representational form of said operational state of said system, based on said representations, said constraints and said criterion, with said representational form comprising a two dimensional array of values related to said set of constraints and to said state of said system, and a one dimensional array of signals related to said operational criterion; and

said two dimensional array defining a polytope in a multidimensional space, with said operational parameters being the variables of said space and said one dimensional array defining a direction in said space;

a second processor portion, responsive to said first processor portion, for transforming said operational parameters, said two dimensional array, and said one dimensional array, onto a transformed space where said state of said system is essentially at the center of said space, and computing a power series function in said transformed space, of order greater than one, that approximates a trajectory curve in consonance with said operational criterion; and

third processor portion, responsive to said second processor portion, for setting said operational parameters of said system at values corresponding to a point in said transformed space and along said curve.

3. Apparatus for allocating resources of a commercial enterprise in accordance with a preselected operational criterion by adjusting values of operational parameters describing said state of said enterprise, said operational parameters being adjustable within a preselected set of linear constraints, characterized by:

sensors for developing said representations of said values of said operational parameters;

a first processing portion, responsive to said signal representations, for projecting said signal representations onto a transformed space to place said state of said enterprise at essentially the center of said transformed space;

a second processing portion, responsive to said first portion, for computing a power series function in said transformed space, of order greater than one, that approximates a trajectory curve in consonance with said operational criterion; and

a controller for setting said operational parameters of said enterprise at values corresponding to a point in said transformed space and along said curve.

4. Apparatus for optimizing operational state of a system described by a set of operational parameters, with said optimizing accomplished by adjusting values of said operational parameters within a preselected set of constraints to minimize a set of preselected operational criterion values, comprising:

sensors for developing signal representations of said values of said operational parameters;

a first processor portion, responsive to said signal representations of said sensors, to applied values of said constraints and to said operational criterion, for developing a canonical form signal representation of said operational state of said system, such that said minimizing is effected by ##EQU23## where x is a vector related to said operational parameters, c is a vector related to said set of preselected criterion values, n is the number of said operational parameters, A=(a₁₁, a₁₂, . . . , a_ij, . . . , a_mn) is an m by n matrix of coefficients related to said preselected set of constraints, and e is a vector of all 1'"'"'s;

said canonical signal representation forming a multidimensional space, with said operational parameters being the variables of said space, said matrix defining a polytope in said space, and said c vector specifying a direction in said space;

a second processor portion, responsive to said first processor portion, for projecting said operational parameters, said matrix, and said c vector unto a transformed space where said state of said system is at essentially a center of said transformed space;

a third processor portion, responsive to said second processor portion, for computing a power series function in said transformed space of order greater than one that approximates a trajectory curve in consonance with said operational criterion; and

a controller, responsive to said third processor portion, for setting said operational parameters of said system at values corresponding to a point in said transformed space and along said curve.

5. Apparatus for optimally scheduling resources of a commercial enterprise in accordance with a preselected operational criterion by adjusting values of operational parameters describing said state of said enterprise, said operational parameters being adjustable within a preselected set of constraints, characterized by:

first means for developing a tentative state-of-the-system representation based on said values of said operational parameters, and for developing a canonical form representation of the operational state of said enterprise corresponding to said tentative state-of-the-system, said constraints and said criterion;

second means, responsive to said first means, for projecting said canonical form representation of said tentative state-of-the-system in response to a "true" activation signal, onto a transformed space to place said state-of-the-system at essentially the center of said space, and computing a power series function in said transformed space, of order greater than one, that approximates a trajectory curve in consonance with said operational criterion;

third means responsive to said second means for modifying said tentative state-of-the-system to correspond to a point in said transformed space and along said curve;

fourth means responsive to said second means for developing said activation control signal, and setting said control signal to "true" state when said tentative state-of-the-system is not within a preselected stopping region, and set to a "false" state when said tentative state-of-the-system is within said preselected stopping region; and

fifth means, responsive to said fourth means, for setting said operational parameters of said enterprise in accordance with said tentative state-of-the-system when said activation control signal is "false".

6. In an electronic resource allocation optimizing apparatus, a method for assigning values to a plurality of controllable parameters of a system, x, where said parameters are linearly related to each other through inequality and equality constraint relationships, and where said assigning values aims to maximize a benefit specified by a linear objective relationship of said parameters characterized by:

a step of transforming said parameters, x, of said system to a domain containing a vector field describing the steepest descent to an optimum allocation, wherein said system parameters are described by a vector signal y; and

a step of passing from a first set of values for said transformed parameters, y(1), that satisfy said constraint relationships to a second set of values for said transformed parameters, y(2), that also satisfy said constraint relationships, in correspondence with the equation ##EQU24## where each of said v_k vector coefficients is related to said first set of values and to said objective relationship, where m is a preselected integer, and t is a preselected step size.

7. The method of claim 6 wherein said step of transforming comprises a projective transformation onto a multidimensional space where said transformed parameters, y(1) are essentially at the center of said space.

8. A method for assigning values to a plurality of controllable parameters of a system, subject to constraints, and where said assigning values aims to maximize a benefit specified by a linear objective relationship of said parameters characterized by:

a step of selecting a starting set of values x for said parameters that satisfy said constraint relationships;

a step of converting said set of values and said objective relationship in accordance with a conversion process that smooths the benefit function in the space of said converted set of values;

a step of developing an m plurality of coefficient sets v_k, where at least one of said coefficients for k>

1 is not zero, related to said converted starting set of values and to said converted objective relationship, where m is a preselected integer;

a step of selecting a step size t; and

a step of obtaining a second set of values for said parameters, y in accordance with the equation ##EQU25##

9. The method of claim 8 wherein said step of converting comprises a projective transformation.

10. The method of claim 8, further comprising a step of iterating through said steps of converting, developing coefficients, selecting step size and obtaining a set of values, where at each iteration following the first iteration said step of selecting a starting set comprises assigning the second set of values, y, of the previous iteration to the first set of values of said each iteration;

and a step of stopping said iterating based on an elevation of a presented stopping rule.

11. A method for assigning values to controllable parameters of a system, where said parameters are linearly related to each other and where said assigning values aims to maximize a benefit specified by a preselected linear relationship of said parameters characterized by

a step of selecting a starting set of values for said parameters that satisfy said constraint relationships;

and

a step of moving from said starting set of values of said parameters by a step of preselected size, t, in accordance with a function that is at least of second order in t, to a new set of values of said parameters.

12. In a system including resources and users of said resources where allocation of said resources to said users is subject to linear constraints, a method for allocating said resources to said users so as to minimize a given objective function comprising the steps of:

treating said resources as variables;

iteratively reassigning said resources from a present tentative allocation to a new tentative allocation in accordance with a polynomial approximation of a curve of order greater than one that is related to said present tentative allocation and is a member of a family of curves that describe a generalized steepest descent to an optimum allocation in accordance with said objective function;

terminating said step of iteratively reassigning said resources when said given objective function is minimized; and

allocating said resources in accordance with the last of said tentative resource reassignments.