US 5,715,165 A · Method and system for scheduling using a facet ascending algorithm or a reduced complexity bundle method for solving an integer programming problem

Abstract

A method and system for scheduling using a facet ascending algorithm or a reduced complexity bundle method for solving an integer programming problem is presented. A Lagrangian dual function of an integer scheduling problem is maximized (for a primal minimization problem) to obtain a good near-feasible solution, and to provide a lower bound to the optimal value of the original problem. The dual function is a polyhedral concave function made up of many facets. The facet ascending algorithm of the present invention exploits the polyhedral concave nature of the dual function by ascending facets along intersections of facets. At each iteration, the algorithm finds the facets that intersect at the current dual point, calculates a direction of ascent along these facets, and then performs a specialized line search which optimizes a scaler polyhedral concave function in a finite number of steps. An improved version of the facet ascending algorithm, the reduced complexity bundle method, maximizes a nonsmooth concave function of variables. This is accomplished by finding a hyperplane separating the origin and the affine manifold of a polyhedron. The hyperplane also separates the origin and the polyhedron since the polyhedron is a subset of its affine manifold. Then an element of the bundle is projected onto the subspace normal to the affine manifold to produce a trial direction normal. If the projection is zero (i.e., indicating the affine manifold contains the origin), a re-projection onto the subspace normal to the affine manifold of an appropriate face of the polyhedron gives a trial direction. This reduced complexity bundle method always finds an .epsilon.-ascent trial direction or detects an .epsilon.-optimal point, thus maintaining global convergence. The method can be used to maximize the dual function of a mixed-integer scheduling problem.

Claims39

Dependent claims

A method for scheduling a sequence of events which are subject to a plurality of constraints, comprising the steps of:

defining the events and constraints in terms of an integer programming expression;
applying Lagrangian relaxation to the integer programming expression to form a Lagrangian dual function;
solving the Lagrangian dual function using a facet ascending algorithm, said facet ascending algorithm calculating an intersection of adjacent facet and moving along the facets on the intersection;
scheduling the sequence of events in accordance with the resolved Lagrangian dual function;
and
performing the events in response to said schedule.

3 more elements

A system for scheduling a sequence of events which are subject to a plurality of constraints comprising:

signal processor for processing information of the events and constraints, and having memory for storing signals including signals defining an executable algorithm for,
(a) defining the events and constraints in terms of an integer programming expression,
(b) applying Lagrangian relaxation to the integer programming expression to form a Lagrangian dual function,
(c) solving the Lagrangian dual function using a facet ascending algorithm stored in said memory means, said facet ascending algorithm calculating an intersection of adjacent facets and moving along the facets on the intersection, and
(d) generating signals indicative of a schedule of the sequence of events in accordance with the resolved Lagrangian dual function;
and
an automated device responsive to said signals indicative of said schedule for automatically performing the events in accordance with said schedule.

4 more elements

A system for scheduling a sequence of events which are subject to a plurality of constraints comprising:

signal processor for processing information of the events and constraints, and having memory for storing signals including signals defining an executable algorithm for,
(a) defining the events and constraints in terms of an integer programming expression,
(b) applying Lagrangian relaxation to the integer programming expression to form a Lagrangian dual function,
(c) solving the Lagrangian dual function using a facet ascending algorithm stored in said memory means, said facet ascending algorithm calculating an intersection of adjacent facets and moving along the facets on the intersection, and
(d) generating signals indicative of a schedule of the sequence of events in accordance with the resolved Lagrangian dual function;
and
a display for generating a display of said schedule in response to said signals indicative thereof.

4 more elements

A method for scheduling a sequence of events which are subject to a plurality of constraints, comprising the steps of:

(1) defining the events and constraints in terms of an expression, said expression defining a nonsmooth concave function;
(2) maximizing said nonsmooth concave function by,
(a) initializing a bundle of .epsilon.-subgradients of said nonsmooth concave function at an iteration point, said bundle including a convex hull having an affine manifold, and
(b) projecting a subgradient of said bundle onto a subspace normal to said affine manifold to locate a trial direction, (i) with a nonzero projection and said trial direction being an .epsilon.-ascent direction updating said iteration point and repeating steps (a) and (b), (ii) with a nonzero projection and said trial direction being other than an .epsilon.-ascent direction adding a subgradient to said bundle and repeating steps (a) and (b), (iii) with a zero projection and an absence of said origin in said convex hull repeating step (b), (iv) with a zero projection and said convex hull containing said origin said nonsmooth concave function is maximized;
(3) scheduling the sequence of events in accordance with said maximized nonsmooth concave function;
and
performing the events in response to said schedule.

4 more elements

A system for scheduling a sequence of events which are subject to a plurality of constraints comprising:

signal processor for processing information of the events and constraints, and having memory for storing signals including signals defining an executable algorithm for,
(1) defining the events and constraints in terms of an expression, said expression defining a nonsmooth concave function,
(2) maximizing said nonsmooth concave function by,
(a) initializing a bundle of .epsilon.-subgradients of said nonsmooth concave function at an iteration point, said bundle including a convex hull having an affine manifold, and
(b) projecting a subgradient of said bundle onto a subspace normal to said affine manifold to locate a trial direction, (i) with a nonzero projection and said trial direction being an .epsilon.-ascent direction updating said iteration point and repeating (a) and (b), (ii) with a nonzero projection and said trial direction being other than an .epsilon.-ascent direction adding a subgradient to said bundle and repeating (a) and (b), (iii) with a zero projection and an absence of said origin in said convex hull repeating (b), (iv) with a zero projection and said convex hull containing said origin said nonsmooth concave function is maximized;
and
(3) generating signals indicative of a schedule of the sequence of events in accordance with said maximized nonsmooth concave function;
and
an automated device responsive to said signals indicative of said schedule for automatically performing the events in accordance with said schedule.

6 more elements

A system for scheduling a sequence of events which are subject to a plurality of constraints comprising:

signal processor for processing information of the events and constraints, and having memory for storing signals including signals defining an executable algorithm for,
(1) defining the events and constraints in terms of an expression, said expression defining a nonsmooth concave function,
(2) maximizing said nonsmooth concave function by,
(a) initializing a bundle of .epsilon.-subgradients of said nonsmooth concave function at an iteration point, said bundle including a convex hull having an affine manifold, and
(b) projecting a subgradient of said bundle onto a subspace normal to said affine manifold to locate a trial direction, (i) with a nonzero projection and said trial direction being an .epsilon.-ascent direction updating said iteration point and repeating (a) and (b), (ii) with a nonzero projection and said trial direction being other than an .epsilon.-ascent direction adding a subgradient to said bundle and repeating (a) and (b), (iii) with a zero projection and an absence of said origin in said convex hull repeating (b), (iv) with a zero projection and said convex hull containing said origin said nonsmooth concave function is maximized;
and
(3) generating signals indicative of a schedule of the sequence of events in accordance with said maximized nonsmooth concave function;
and
a display for generating a display of said schedule in response to said signals indicative thereof.

6 more elements

Dependencies are inferred from the claim text.

Method and system for scheduling using a facet ascending algorithm or a reduced complexity bundle method for solving an integer programming problem

Life of this patent

Method and system for scheduling using a facet ascending algorithm or a reduced complexity bundle method for solving an integer programming problem

Life of this patent

Abstract

Claims39