LP relaxation modification and cut selection in a MIP solver

• US 8,463,729 B2
• Filed: 12/01/2009
• Issued: 06/11/2013
• Est. Priority Date: 12/01/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Achterberg, Tobias
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): PELLETT, DANIEL T
• Application Number:
  US12/628,837
• Publication Number:
  US 20110131167A1
• Time in Patent Office: 1,288 Days
• Field of Search: None
• US Class Current: 706/47
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

Mixed integer programs (MIP) are solved by constructing and solving associated linear programming (LP) relaxation problems. The LP relaxations are iteratively constructed through the introduction of cutting planes that are derived using one solution of an LP, then filtered based on an alternative solution to the LP. The LP relaxation is constructed, and its alternate solution is derived, to efficiently converge to a solution for the MIP.

Claims

1. A machine implemented method of determining an allocation of physical resources comprising:

(a) receiving a mixed integer programming (MIP) model and an outcome objective;

(b) deriving a relaxation linear programming model (LP) associated with the MIP model;

(c) applying a processor to the LP to compute a first optimal LP solution;

(d) finding a set of cutting planes that separate the first optimal LP solution from a set of integer feasible solutions;

(e) applying a processor to the LP to compute a second optimal LP solution, where the second optimal LP solution is different than the first optimal LP solution;

(f) applying cut filtering on the set of cutting planes, using the second optimal LP solution as a reference solution such that only cutting planes that are violated by the first and second optimal LP solution are allowed to survive; and

(g) applying cutting planes that survived the cut filtering to derive a new LP.

2. The method of claim 1, wherein the new LP derived in claim 1 item (g) is used as the LP of claim 1 item (b) in a subsequent iteration of the method.

3. The method of claim 2, comprising, when no cuts survive the cut filtering of item (f):

using the second optimal LP solution in a subsequent MIP solution process to find an optimal MIP solution; and

providing the optimal MIP solution to a user.

4. The method of claim 3, comprising:

allocating physical resources based on the optimal MIP solution.

5. A computer program product comprising a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising instructions for:

(a) receiving a mixed integer programming (MIP) model and an outcome objective;

(b) deriving a relaxation linear programming model (LP) associated with the MIP model;

(c) applying a processor to the LP relaxation model to compute an optimal LP solution;

(d) finding a set of cutting planes that separate the optimal solution of (b) from a set of integer feasible solutions;

(e) finding an alternate optimal solution to the LP relaxation model;

(f) applying cut filtering on the set of cutting planes, using the optimal solution of (e) as a reference solution such that only cutting planes that are violated by the first and second optimal LP solution are allowed to survive;

(g) applying cutting planes that survived the cut filtering to derive a new LP.

6. The computer program product of claim 5, comprising instructions for using the new LP derived in claim 5 item (g) as the LP of claim 5 item (b) in a subsequent iteration of the method.

7. The computer program product of claim 5, comprising instructions for, when no cuts survive the cut filtering of item (f):

using the second optimal LP solution in a subsequent MIP solution process to find an optimal MIP solution; and

providing the optimal MIP solution to a user.

8. A machine-implemented method of allocating physical resources using a model comprising a mixed integer program (MIP) and using an original LP relaxation of the MIP having variables, slacks, and an objective function, the method comprising:

solving the original LP relaxation of the MIP to obtain a first optimal LP relaxation solution; and

finding a second alternative LP relaxation solution, comprising;

(i) solving the original LP relaxation of the MIP to obtain an initial LP relaxation solution;

(ii) fixing variables and slacks with non-zero reduced costs, and setting the objective function to zero to obtain a modified LP relaxation;

(iii) at least some of the time, reducing the size of the modified LP relaxation by any combination of;

applying linear presolving;

applying clique table propagation; and

/or fixing non-basic variables randomly;

(iv) further modifying the LP relaxation by one of fixing some of the variables; and

modifying the objective function;

(v) solving the modified LP relaxation to obtain a modified LP relaxation solution;

(vi) choosing a better solution between a current best LP relaxation solution and the modified LP relaxation solution to obtain a new current best LP relaxation solution;

(vii) converting the current best LP relaxation solution into a primal feasible basis for the original LP relaxation;

(viii) attempting to solve the original LP relaxation starting from said primal feasible basis; and

(ix) if step (viii) was successful, using a resulting basis in a subsequent MIP solving process using cutting planes, in which only cutting planes that are violated by both the first and second optimal LP solutions are allowed to survive.

9. The method of claim 8, further comprising repeating steps (iv)-(vi) until one of the following:

all integer variables are at their bounds;

or steps (iv)-(vi) have been repeated a certain number of times without the modified LP relaxation solution being better than the current best LP relaxation solution.

10. The method of claim 8, in step (iv) of which modifying the objective function comprises:

installing a new objective function for the modified LP relaxation based on a last LP relaxation solution; and

installing a very large or very small objective coefficient for each of some randomly chosen variables in the modified LP relaxation.

11. The method of claim 10, in step (iv) of which fixing some of the variables comprises fixing a random subset of variables that have been assigned very large or very small objective coefficients at step (iv) of a previous iteration of a loop comprising steps (iv)-(vi).

12. The method of claim 8, wherein the solving of step (v) comprises applying a dual simplex algorithm if variables have been fixed, and applying a primal simplex algorithm if objective coefficients have been changed.

13. The method of claim 8, in step (viii) of which attempting to solve the original LP relaxation is performed subject to an iteration limit.

14. A computer program product for allocating physical resources using a model comprising a mixed integer program (MIP) and using an original LP relaxation of the MIP having variables, slacks, and an objective function, comprising a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising instructions for:

solving the original LP relaxation of the MIP to obtain a first optimal LP relaxation solution; and

finding a second alternative LP relaxation solution, comprising instructions for;

(i) solving the original LP relaxation of the MIP to obtain an initial LP relaxation solution;

(ii) fixing variables and slacks with non-zero reduced costs, and setting the objective function to zero to obtain a modified LP relaxation;

(iii) at least some of the time, reducing the size of the modified LP relaxation by any combination of;

applying linear presolving;

applying clique table propagation; and

/or fixing non-basic variables randomly;

(iv) further modifying the LP relaxation by one of fixing some of the variables; and

modifying the objective function;

(v) solving the modified LP relaxation to obtain a modified LP relaxation solution;

(vi) choosing a better solution between a current best LP relaxation solution and the modified LP relaxation solution to obtain a new current best LP relaxation solution;

(vii) converting the current best LP relaxation solution into a primal feasible basis for the original LP relaxation;

(viii) attempting to solve the original LP relaxation starting from said primal feasible basis; and

(ix) if step (viii) was successful, using a resulting basis in a subsequent MIP solving process using cutting planes, in which only cutting planes that are violated by both the first and second optimal LP solutions are allowed to survive.

15. The computer program product of claim 14, further comprising instructions for repeating steps (iv)-(vi) until one of the following:

all integer variables are at their bounds;

or steps (iv)-(vi) have been repeated a certain number of times without the modified LP relaxation solution being better than the current best LP relaxation solution.

16. The computer program product of claim 14, in step (iv) of which modifying the objective function comprises instructions for:

installing a new objective function for the modified LP relaxation based on a last LP relaxation solution; and

installing a very large or very small objective coefficient for each of some randomly chosen variables in the modified LP relaxation.

17. The computer program product of claim 16, in step (iv) of which fixing some of the variables comprises instructions for fixing a random subset of variables that have been assigned very large or very small objective coefficients at step (iv) of a previous iteration of a loop comprising steps (iv)-(vi).

18. The computer program product of claim 14, wherein the solving of step (v) comprises instructions for applying a dual simplex algorithm if variables have been fixed, and applying a primal simplex algorithm if objective coefficients have been changed.

19. The computer program product of claim 14, in step (viii) of which attempting to solve the original LP relaxation comprises instructions for attempting to solve the original LP relaxation subject to an iteration limit.

20. A MIP solver comprising:

one or more processors for executing instructions;

one or more memories storing instructions and coupled to said one or more processors, the one or more processors and the one or more memories being configured for;

(a) receiving a mixed integer programming (MIP) model and an outcome objective;

(b) deriving a relaxation linear programming model (LP) associated with the MIP model;

(c) applying a processor to the LP to compute a first optimal LP solution;

(d) finding a set of cutting planes that separate the first optimal LP solution from a set of integer feasible solutions;

(e) applying a processor to the LP to compute a second optimal LP solution, where the second optimal LP solution is different than the first optimal LP solution;

(f) applying cut filtering on the set of cutting planes, using the second optimal LP solution as a reference solution such that only cutting planes that are violated by the first and second optimal LP solution are allowed to survive; and

(g) applying cutting planes that survived the cut filtering to derive a new LP.

21. The MIP solver of claim 20, wherein the one or more processors and the one or more memories are configured such that the new LP derived in claim 22 item (g) is used as the LP of claim 22 item (b) in a subsequent iteration.

22. The MIP solver of claim 21, comprising an output device coupled to the one or more processors, wherein the one or more processors and the one or more memories are configured for, when no cuts survive the cut filtering of item (f):

using the second optimal LP solution in a subsequent MIP solution process to find an optimal MIP solution; and

providing the optimal MIP solution to a user via the output device.

23. A MIP solver for allocating physical resources using a model comprising a mixed integer program (MIP) and using an original LP relaxation of the MIP having variables, slacks, and an objective function, comprising:

one or more processors for executing instructions;

one or more memories storing instructions and coupled to said one or more processors, the one or more processors and the one or more memories being configured for;

solving the original LP relaxation of the MIP to obtain a first optimal LP relaxation solution; and

finding a second alternative LP relaxation solution, comprising;

(i) solving the original LP relaxation of the MIP to obtain an initial LP relaxation solution;

(ii) fixing variables and slacks with non-zero reduced costs, and setting the objective function to zero to obtain a modified LP relaxation;

(iii) at least some of the time, reducing the size of the modified LP relaxation by any combination of;

applying linear presolving;

applying clique table propagation; and

/or fixing non-basic variables randomly;

(iv) further modifying the LP relaxation by one of fixing some of the variables; and

modifying the objective function;

(v) solving the modified LP relaxation to obtain a modified LP relaxation solution;

(vi) choosing a better solution between a current best LP relaxation solution and the modified LP relaxation solution to obtain a new current best LP relaxation solution;

(vii) converting the current best LP relaxation solution into a primal feasible basis for the original LP relaxation;

(viii) attempting to solve the original LP relaxation starting from said primal feasible basis; and

(ix) if step (viii) was successful, using a resulting basis in a subsequent MIP solving process using cutting planes, in which only cutting planes that are violated by both the first and second optimal LP solutions are allowed to survive.

24. The MIP solver of claim 23, wherein the one or more processors and the one or more memories are configured for repeating steps (iv)-(vi) until one of the following:

all integer variables are at their bounds;

or steps (iv)-(vi) have been repeated a certain number of times without the modified LP relaxation solution being better than the current best LP relaxation solution.

25. The MIP solver of claim 23, wherein the one or more processors and the one or more memories are configured for, in step (iv), modifying the objective function by:

installing a new objective function for the modified LP relaxation based on a last LP relaxation solution; and

installing a very large or very small objective coefficient for each of some randomly chosen variables in the modified LP relaxation.

26. The MIP solver of claim 25, wherein the one or more processors and the one or more memories are configured for, in step (iv), fixing some of the variables by fixing a random subset of variables that have been assigned very large or very small objective coefficients at step (iv) of a previous iteration of a loop comprising steps (iv)-(vi).

27. The MIP solver of claim 23, wherein the one or more processors and the one or more memories are configured for, in step (v), applying a dual simplex algorithm if variables have been fixed, and applying a primal simplex algorithm if objective coefficients have been changed.