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

• US 5,715,165 A
• Filed: 12/23/1994
• Issued: 02/03/1998
• Est. Priority Date: 12/23/1994
• Status: Expired due to Fees

• Current Assignee: University of Connecticut (State of Connecticut)
• Original Assignee: University of Connecticut (State of Connecticut)
• Inventors: Tomastik, Robert N., Luh, Peter B.
• Primary Examiner(s): Gordon, Paul P.
• Application Number:
  US08/363,216
• Time in Patent Office: 1,138 Days
• Field of Search: 364/468.09, 364/140, 364/141, 364/148, 364/152, 364/153, 364/468.01, 364/468.03, 364/468.05, 364/468.06, 364/474.15, 395/208, 395/209
• US Class Current: 700/173
• CPC Class Codes: G06F 18/24317 Piecewise classification, i.e. whereby each classification requires several discriminant rules
• CPC Class Codes: G06F 18/2451 linear, e.g. hyperplane
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

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 ε-ascent trial direction or detects an ε-optimal point, thus maintaining global convergence. The method can be used to maximize the dual function of a mixed-integer scheduling problem.

Claims

1. 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.

2. The method of claim 1 wherein said step of solving the Lagrangian dual function using said facet ascending algorithm, comprises the steps of:

(1) performing a line search of the Lagrangian dual function along a direction of ascent;

(2) updating the Lagrange multipliers based on the line search results;

(3) locating a subspace formed by the intersection of facets at the updated Lagrange multipliers;

(4) determining a direction of ascent within the subspace formed by the intersection of facets; and

repeating steps (1)-(4) until a stopping criteria is met.

3. The method of claim 1 wherein:

said integer programming expression comprises ##EQU28## where J_i (x_i), H_ij (x_i), and h_ik (x_i) are real-valued functions that map Zⁿⁱ →

R, ##EQU29## is an n×

1 vector of decision variables with n=Σ

_i=1¹ n_i and lower and upper bounds x¹ and x^u, respectively, and Z is a set of integers;

said Lagrangian dual function comprises an expression ##EQU30## where ##EQU31## subject to h_ik (x_i)=0, i=1, . . . , I;

k=1, . . . , K_i ; and

said step solving the Lagrangian dual function using said facet ascending algorithm comprises the steps of,

(1) initializing parameters

(a) set k=0,

(b) initialize u⁰,

(c) compute a subgradient g(u⁰), and

(d) set d⁰ =g(u⁰);

(2) performing a line search along d^k to obtain α

₁, α

₂, and α

*;

(3) updating u;

u^k+1 =u^k +α

*d^k,

(4) stopping when a stopping criteria is met,

(5) from points u_a =u^k +α

₁ d^k and u_b =u^k +α

₂ d^k, where α

₁ and α

₂ result from the line search of step (2) at a current iteration, initialize a matrix S= g_a^T -g_b^T !, where g_a =g(u_a) and g_b =g(u_b),

(6) evaluating d= I-S^T (S^T)^-1 S!g_a, if d=0,

(a) solving S^T μ

=g_a,

(b) letting λ

_i =μ

_i for i ε

D-a, λ

_a =1-Σ

_iε

D-α

λ

_i,

(c) for w ε

D such that λ

_w <

0, if w≠

α

, removing a row g_a^T -g_w^T from S and forming d= I-S^T (S^T)^-1 S!g_a, if w=α

, subtracting a first row of S from all other rows and subsequently removing the first row, then forming d= I-S^T (S^T)^-1 S!g_b,

(7)from u^k+1, moving a step ε

in a direction d and computing J_LR (u^k+1 +ε

d) and a subgradient g.sub.ν

=g(u^k+1 +ε

d), if g.sub.ν

^T d=d^T d, setting d^k+1 =d, incrementing k by 1, and go to step (2), and

(8) adding a row (g_a -g.sub.ν

)^T to S and go to step (6).

4. The method of claim 3 wherein said step of stopping when said stopping criteria is met includes using heuristics to obtain a primal solution.

5. The method of claim 2 wherein said stopping criteria includes using heuristics to obtain a primal solution.

6. 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.

7. The system of claim 6 wherein said solving the Lagrangian dual function using said facet ascending algorithm, comprises:

(1) performing a line search of the Lagrangian dual function along a direction of ascent;

(2) updating the Lagrange multipliers based on the line search results;

(3) locating a subspace formed by the intersection of facets at the updated Lagrange multipliers;

(4) determining a direction of ascent within the subspace formed by the intersection of facets; and

repeating (1)-(4) until a stopping criteria is met.

8. The system of claim 6 wherein:

said integer programming expression comprises ##EQU32## where J_i (x_i), H_ij (x_i), and h_ik (x_i) are real-valued functions that map Zⁿⁱ →

R, ##EQU33## is an n×

1 vector of decision variables with n=Σ

¹_i=1 n_i and lower and upper bounds x¹ and x^u, respectively, and Z is a set of integers;

said Lagrangian dual function comprises an expression ##EQU34## subject to h_ik (x_i)=0, i=1, . . . , I;

K=1, . . . , K_i ; and

said solving the Lagrangian dual function using said facet ascending algorithm comprises the steps of,

(1) initializing parameters

(a) set k=0,

(b) initialize u⁰,

(c) compute a subgradient g(u⁰), and

(d) set d⁰ =g(u⁰);

(2) performing a line search along d^k to obtain α

₁, α

₂, and α

*,

(3) updating u;

u^k+1 =u^k +α

*d^k,

(4) stopping when a stopping criteria is met,

(5) from points u_a =u^k +α

₁ d^k and u_b =u^k +α

₂ d^k, where α

₁ and α

₂ result from the line search at a current iteration, initialize a matrix S= g_a^T -g^T_b !, where g_a =g(u_a) and g_b =g(u_b),

(6) evaluating d= I-S^T (S^T)^-1 S!g_a, if d=0,

(a) solving S^T μ

=g_a,

(b) letting λ

_i =μ

_i for i ε

D-α

, λ

_a =1-Σ

_iε

D-α

λ

_i,

(c) for w ε

D such that λ

_w <

0, if w≠

α

, removing a row g_a^T -g_w^T from S and forming d= I-S^T (S^T)^-1 S!g_a, if w=α

, subtracting a first row of S from all other rows and subsequently removing the first row, then forming d= I-S^T (S^T)^-1 S!g_b,

(7) from u^k+1, moving a step ε

in a direction d and computing J_LR (u^k+1 +ε

d) and a subgradient g.sub.ν

=g(u^k+1 +ε

d), if g.sub.ν

^T d=d^T d, setting d^k+1 =d, incrementing k by 1, and go to (2), and

(8) adding a row (g_a -g.sub.ν

)^T to S and go to (6).

9. The system of claim 7 wherein said stopping criteria includes using heuristics to obtain a primal solution.

10. The system of claim 8 wherein said stopping criteria includes using heuristics to obtain a primal solution.

11. 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.

12. The system of claim 11 wherein said solving the Lagrangian dual function using said facet ascending algorithm, comprises:

(1) performing a line search of the Lagrangian dual function along a direction of ascent;

(2) updating the Lagrange multipliers based on the line search results;

(3) locating a subspace formed by the intersection of facets at the updated Lagrange multipliers;

(4) determining a direction of ascent within the subspace formed by the intersection of facets; and

repeating (1)-(4) until a stopping criteria is met.

13. The system of claim 12 wherein said stopping criteria includes using heuristics to obtain a primal solution.

14. The system of claim 11 wherein:

said integer programming expression comprises ##EQU35## where J_i (x_i), H_ij (x_i), and h_ik (x_i) are real-valued functions that map Zⁿⁱ →

R, ##EQU36## is an n×

1 vector of decision variables with n=Σ

_i=1¹ n_i and lower and upper bounds x¹ and x^u, respectively, and Z is a set of integers;

said Lagrangian dual function comprises an expression ##EQU37## subject to h_ik (x_i)=0, i=1, . . . , I;

k=1, . . . , K_i ; and

said solving the Lagrangian dual function using said facet ascending algorithm comprises the steps of,

(1) initializing parameters

(a) set k=0,

(b) initialize u⁰,

(c) compute a subgradient g(u⁰), and

(d) set d⁰ =g(u⁰);

(2) performing a line search along d^k to obtain α

₁, α

₂, and α

*;

(3) updating u;

u^k+1 =u^k +α

*d^k,

(4) stopping when a stopping criteria is met,

(5) from points u_a =u^k +α

₁ d^k and u_b =u^k +α

₂ d^k, where α

₁ and α

₂ result from the line search at a current iteration, initialize a matrix S= g_a^T -g_b^T !, where g_a =g(u_a) and g_b =g(u_b),

(6) evaluating d= I-S^T (S^T)⁺¹ S!g_a, if d=0,

(a) solving S^T μ

=g_a,

(b) letting λ

_i =μ

_i for i ε

D-α

, λ

_a =1-Σ

_iε

D-α

λ

_i,

(c) for w ε

D such that λ

_w <

0, if w≠

α

, removing a row g_a^T -g_w^T from S and forming d= I-S^T (S^T)^-1 S!g_a, if w=α

, subtracting a first row of S from all other rows and subsequently removing the first row, then forming d= I-S^T (S^T)^-1 S!g_b,

(7) from u^k+1, moving a step ε

in a direction d and computing J_LR (u^k+1 +ε

d) and a subgradient g.sub.ν

=g(u^k+1 +ε

d), if g.sub.ν

^T d=d^T d, setting d^k+1 =d, incrementing k by 1, and go to (2), and

(8) adding a row (g_a -g.sub.ν

)^T to S and go to (6).

15. The system of claim 13 wherein said stopping criteria includes using heuristics to obtain a primal solution.

16. 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;

generating a dual function decoupled by multipliers from said integer programming expression, said dual function is a polyhedral concave function comprised of many facets;

solving the dual function using a facet ascending algorithm, said facet ascending algorithm calculating an intersection of adjacent facets and moving along the facets at the intersection thereof;

scheduling the sequence of events in accordance with the resolved dual functional and

performing the events in response to said schedule.

17. The method of claim 16 wherein said step of solving the dual function using said facet ascending algorithm, comprises the steps of:

(1) performing a line search of the dual function along a direction of ascent;

(2) updating the multipliers based on the line search results;

(3) locating a subspace formed by the intersection of the facets at the updated multipliers;

(4) determining a direction of ascent within the subspace formed by the intersection of the facets; and

repeating steps (1)-(4) until a stopping criteria is met.

18. The method of claim 17 wherein said stopping criteria includes using heuristics to obtain a primal solution.

19. The system of claim 17 wherein said stopping criteria includes using heuristics to obtain a primal solution.

20. 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) generating a dual function decoupled by multipliers from said integer programming expression, said dual function is a polyhedral concave function comprised of many facets,

(c) solving the dual function using a facet ascending algorithm, said facet ascending algorithm calculating an intersection of adjacent facets and moving along the facets at the intersection thereof, and

(d) generating signals indicative of a schedule of the sequence of events in accordance with the resolved dual function; and

an automated device responsive to said signals indicative of said schedule for automatically performing the events in accordance with said schedule.

21. The system of claim 20 wherein said solving the dual function using said facet ascending algorithm, comprises:

(1) performing a line search of the dual function along a direction of ascent;

(2) updating the multipliers based on the line search results;

(3) locating a subspace formed by the intersection of the facets at the updated multipliers;

(4) determining a direction of ascent within the subspace formed by the intersection of the facets; and

repeating (1)-(4) until a stopping criteria is met.

22. 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) generating a dual function decoupled by multipliers from said integer programming expression, said dual function is a polyhedral concave function comprised of many facets,

(c) solving the dual function using a facet ascending algorithm, said facet ascending algorithm calculating an intersection of adjacent facets and moving along the facets at the intersection thereof, and

(d) generating signals indicative of a schedule of the sequence of events in accordance with the resolved dual function; and

a display for generating a display of said schedule in response to said signals indicative thereof.

23. The system of claim 22 wherein said solving the dual function using said facet ascending algorithm, comprises:

(1) performing a line search of the dual function along a direction of ascent;

(2) updating the multipliers based on the line search results;

(3) locating subspace forced by the intersection of the facets at the updated multipliers;

(4) determining a direction of ascent within the subspace formed by the intersection of the facets; and

repeating (1)-(4) until a stopping criteria is met.

24. The system of claim 23 wherein said stopping criteria includes using heuristics to obtain a primal solution.

25. 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 ε

-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 ε

-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 ε

-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.

26. The method of claim 25 wherein said expression defining said nonsmooth concave function comprises:

##EQU38## where f(x) is Lipschitzian, and for a given value x, returns f(x) and exactly one arbitrary subgradient at x, and a subgradient g is a n-vector in a subdifferential ∂

f(x) defined as,

space="preserve" listing-type="equation">∂

f(x)={gε

R.sup.n ;

f(y)≦

f(x)+g.sup.T (y-x),∀

yε

R.sup.n }

whereby the Lipschitz property of f implies that all subgradients are finite, ∂

f exists everywhere, and ∂

f is a nonempty compact convex set in Rⁿ.

27. The method of claim 26 wherein said affine manifold A of said convex hull P for said bundle B_b ={g₁, g₂, . . . ,g_b }, b≧

2, P_b =conv{B_b }, where g is a subgradient, is expressed in matrix form as;

##EQU39##

28. The method of claim 27 wherein a direction of projection is determined by:

space="preserve" listing-type="equation">d=g-{S.sub.b.sup.T (S.sub.b S.sub.b.sup.T).sup.-1 (S.sub.b g)!}

29. The method of claim 28 with a zero projection and an absence of said origin in said convex hull repeating step (b) comprises:

computing σ

=(S_b S_b^T)^-1 S_b g;

letting λ

_i =σ

_i-1 for i=2,3, . . . , b, and ##EQU40## for any one λ

_j <

0, form B_b-1 ={B_b -g_j }, with only one subgradient in B_b-1 let d=g, gε

B_b-1 ; and

with other than only one subgradient project said subgradient g by, d=g{S_b^T-1 (S_b-1 S_b-1^T)^-1 (S_b-1 g)!} where S_b-1 has rows (g_k -g_i)^T, for one g_k ε

B_b-1 and for all g_i ε

B_b-1 -g_k.

30. 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 ε

-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 ε

-ascent direction updating said iteration point and repeating (a) and (b), (ii) with a nonzero projection and said trial direction being other than an ε

-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.

31. The system of claim 30 wherein said expression defining said nonsmooth concave function comprises:

##EQU41## where f(x) is Lipschitzian, and for a given value x, returns f(x) and exactly one arbitrary subgradient at x, and a subgradient g is a n-vector in a subdifferential ∂

f(x) defined as,

space="preserve" listing-type="equation">∂

f(x)={gε

R.sup.n ;

f(y)≦

f(x)+g.sup.T (y-x),∀

yε

R.sup.n }

whereby the Lipschitz property of f implies that all subgradients are finite, ∂

f exists everywhere, and ∂

f is a nonempty compact convex set in Rⁿ.

32. The system of claim 31 wherein said affine manifold A of said convex hull P for said bundle B_b ={g₁, g₂, . . . , g_b }, b≧

2, P_b =conv{B_b }, where g is a subgradient, is expressed in matrix form as;

##EQU42##

33. The system of claim 32 wherein a direction of projection is determined by:

space="preserve" listing-type="equation">d=g-{S.sub.b.sup.T (S.sub.b S.sub.b.sup.T).sup.-1 (S.sub.b g)!}

34. The system of claim 33 with a zero projection and an absence of said origin in said convex hull repeating step (b) comprises:

computing σ

=(S_b S_b^T)^-1 S_b g;

letting λ

_i =σ

_i-1 for i=2,3, . . . ,b, and ##EQU43## for any one λ

_j <

0, form B_b-1 ={B_b -g_j }, with only one subgradient in B_b-1 let d=g, gε

B_b-1 ; and

with other than only one subgradient project said subgradient g by, d=g{S_b-1^T (S_b-1 S_b-1^T)^-1 (S_b-1 g)!} where S_b-1 has rows (g_k g_i)^T, for one g_k ε

B_b-1 and for all g_i ε

B_b-1 -g_k.

35. 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 ε

-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 ε

-ascent direction updating said iteration point and repeating (a) and (b), (ii) with a nonzero projection and said trial direction being other than an ε

-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.

36. The system of claim 35 wherein said expression defining said nonsmooth concave function comprises:

##EQU44## where f(x) is Lipschitzian, and for a given value x, returns f(x) and exactly one arbitrary subgradient at x, and a subgradient g is a n-vector in a subdifferential ∂

f(x) defined as,

space="preserve" listing-type="equation">∂

f(x)={gε

R.sup.n ;

f(y)≦

f(x)+g.sup.T (y-x),∀

yε

R.sup.n }

whereby the Lipschitz property of f implies that all subgradients are finite, ∂

f exists everywhere, and ∂

f is a nonempty compact convex set in Rⁿ.

37. The system of claim 36 wherein said affine manifold A of said convex hull P for said bundle B_b ={g₁, g₂, . . . , g_b }, b≧

2, P_b =conv{B_b }, where g is a subgradient, is expressed in matrix form as;

##EQU45##

38. The system of claim 37 wherein a direction of projection is determined by:

space="preserve" listing-type="equation">d=g-{S.sub.b.sup.T (S.sub.b S.sub.b.sup.T).sup.-1 (S.sub.b g)!}

39.

39. The system of claim 38 with a zero projection and an absence of said origin in said convex hull repeating step (b) comprises:

computing σ

=(S_b S_b^T)^-1 S_b g;

letting λ

_i =σ

_i-1 for i=2,3, . . . , b, and ##EQU46## for any one λ

_j <

0, form B_b-1 ={B_b -g_i }, with only one subgradient in B_b-1 let d=g, g ε

B_b-1 ; and

with other than only one subgradient project said subgradient g by, d=g{S_b-1^T (S_b-1 S_b-1^T)^-1 (S_b-1 g)!} where S_b-1 has rows (g_k -g_i)^T, for one g_k ε

B_b-1 and for all g_i ε

B_b-1 -g_k.