LP relaxation modification and cut selection in a MIP solver
First Claim
Patent Images
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 filtering on the set of cutting planes, using the second optimal LP solution as a reference solution; and
(g) applying cuts that survived the cut filtering to derive a new LP.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
30 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 filtering on the set of cutting planes, using the second optimal LP solution as a reference solution; and (g) applying cuts that survived the cut filtering to derive a new LP. - View Dependent Claims (2, 3, 4)
-
-
5. A computer program product comprising a 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 filtering on the set of cutting planes, using the optimal solution of (e) as a reference solution; (g) applying cuts that survived the cut filtering to derive a new LP. - View Dependent Claims (6, 7)
-
-
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
/orfixing 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 (vii) was successful, using a resulting basis in a subsequent MIP solving process. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. 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 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
/orfixing 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 (vii) was successful, using a resulting basis in a subsequent MIP solving process. - View Dependent Claims (16, 17, 18, 19, 20, 21)
-
-
22. 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 filtering on the set of cutting planes, using the second optimal LP solution as a reference solution; and (g) applying cuts that survived the cut filtering to derive a new LP. - View Dependent Claims (23, 24)
-
-
25. 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
/orfixing 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 (vii) was successful, using a resulting basis in a subsequent MIP solving process. - View Dependent Claims (26, 27, 28, 29, 30)
-
Specification