Systems and methods for conflict resolution and stabilizing cut generation in a mixed integer program solver

Patent metadata

Field	Value
Publication number	US-9524471-B2
Application number	US-201314068581-A
Country	US
Kind code	B2
Filing date	Oct 31, 2013
Priority date	Oct 31, 2012
Publication date	Dec 20, 2016
Grant date	Dec 20, 2016

Abstract

Systems and methods for conflict resolution and stabilizing cut generation in a mixed integer linear program (MILP) solver are disclosed. One disclosed method includes receiving a mixed integer linear problem (MILP), the MILP having a root node and one or more global bounds; pre-processing the MILP, the MILP being associated with nodes; establishing a first threshold for a learning phase branch-and-cut process; performing, by one or more processors, the learning phase branch-and-cut process for nodes associated with the MILP, wherein performing the learning phase branch-and-cut process includes: evaluating the nodes associated with the MILP, collecting conflict information about the MILP, and determining whether the first threshold has been reached; responsive to reaching the first threshold, removing all of the nodes and restoring a root node of the MILP; and solving, with the one or more processors, the MILP using the restored root node and the collected conflict information.

First claim

That which is claimed is:

1. A computer-program product, tangibly embodied in a non-transitory machine-readable storage medium, including instructions configured to cause a data processing apparatus to:
receive a mixed integer linear problem (MILP), the MILP having one or more global bounds, the MILP having associated nodes;
pre-process the MILP;
establish a first threshold for a learning-phase branch-and-cut process;
perform a first phase of a two-phase branch-and-cut process, wherein the first phase is the learning phase branch-and-cut process for nodes associated with the MILP in a first branch-and-bound tree, and wherein performing the learning phase branch-and-cut process includes:
evaluating the nodes associated with the MILP,
collecting conflict information about the MILP;
determining whether the first threshold has been reached,
responsive to reaching the first threshold:
pruning all of the nodes;
restoring a root node of the MILP;
updating one or more of the global bounds based on the collected conflict information;
storing initial costs from the learning phase branch-and-cut process; and

perform a second phase of the two-phase branch-and-cut process after the first phase, wherein the second phase is an application phase branch-and-cut process for nodes associated with the MILP in a second branch-and-bound tree, and wherein performing the application phase branch-and-cut process includes:
evaluating the restored root node; and
solving the MILP using the restored root node, the stored initial costs, and the collected conflict information;
wherein performing the application phase branch-and-cut process does not include collecting conflict information about the MILP or determining whether the first threshold has been reached.

2. The computer-program product of claim 1 , wherein instructions to cause the data processing apparatus to perform a learning phase branch-and-cut process includes instructions to cause the data processing apparatus to determine an infeasible sub-problem.

3. The computer-program product of claim 1 , wherein instructions to cause the data processing apparatus to evaluate the nodes associated with the MILP comprises instructions for identifying a conflict node, and wherein instructions to cause the data processing apparatus to collect conflict information comprises instructions to cause the data processing apparatus to:
perform an infeasibility analysis on the identified conflict node to derive one or more conflict clauses based on the identified conflict node; and
storing the one or more conflict clauses.

4. The computer-program product of claim 1 , wherein instructions to cause the data processing apparatus to preprocess the MILP comprise instructions to cause the data processing apparatus to:
determine and eliminate redundant constraints of the MILP; and
determine and eliminate fixed variables of the MILP.

5. A system comprising:
a computer-readable medium; and
a processor in communication with the computer readable medium, the processor configured to read and execute instructions stored in the computer-readable medium to perform operations comprising:
receiving a mixed integer linear problem (MILP), the MILP having a root node and one or more global bounds;
pre-processing the MILP;
establishing a first threshold for a learning-phase branch-and-cut process;
performing a first phase of a two-phase branch-and-cut process, wherein the first phase is the learning phase branch-and-cut process on nodes associated with the MILP in a first branch-and-bound tree, and wherein performing the learning phase branch-and-cut process includes:
evaluating a plurality of the nodes associated with the MILP,
collecting conflict information about the MILP, and
determining whether the first threshold has been reached;

responsive to reaching the first threshold, pruning all of the nodes, restoring the root node of the MILP, updating one or more of the global bounds based on the collected conflict information, and storing initial costs from the learning phase branch-and-cut process; and
perform a second phase of the two-phase branch-and-cut process after the first phase, wherein the second phase is an application phase branch-and-cut process for nodes associated with the MILP in a second branch-and-bound tree, and wherein performing the application phase branch-and-cut process includes:
evaluating the restored root node; and
solving the MILP using the restored root node, the stored initial costs, and the collected conflict information;
wherein performing the application phase branch-and-cut process does not include collecting conflict information about the MILP or determining whether the first threshold has been reached.

6. The system of claim 5 , wherein performing the learning phase branch-and-cut process comprises determining an infeasible sub-problem by determining a clause of the MILP evaluates as false.

7. The system of claim 5 , wherein determining one or more conflict clauses comprises:
identifying a conflict node;
performing an infeasibility analysis on the conflict node;
deriving one or more conflict clauses based on the conflict node; and
storing the one or more conflict clauses.

8. The system of claim 5 , wherein pre-processing the MILP comprises:
determining and eliminating redundant constraints of the MILP; and
determining and eliminating fixed variables.

9. The system of claim 5 , further comprising establishing a second threshold, and wherein the learning phase branch-and-cut process further comprises determining whether the second threshold has been reached, and responsive to reaching either the first or second thresholds, removing all of the nodes and restoring the root node of the MILP.

10. A system comprising:
a computer-readable medium; and
a processor in communication with the computer readable medium, the processor configured to read and execute instructions stored in the computer-readable medium to perform a method, the method comprising:
analyzing a mixed integer linear problem (MILP) to determine an initial linear problem (LP) solution, the analyzing includes determining whether the initial LP solution is non-optimal;
responsive to determining the initial LP solution is non-optimal, generating a sub-MILP of the MILP;
determining one or more new objectives of the sub-MILP, each of the one or more new objective different from the one or more objectives of the MILP, wherein determining the one or more objectives of the sub-MILP comprises:
determining pseudo-costs associated with the sub-MILP;
determining one or more high-impact variables based on the determined pseudo-costs, the one or more high-impact variables including a variable that can be held constant or whose bounds can be improved to reduce a solution time of the MILP; and
changing a coefficient of at least one of the one or more high-impact variables;

generating cuts based on the one or more new objectives;
analyzing the sub-MILP based on the cuts to determine a new LP solution and new bounds; and
solving the MILP based on the new LP solution and the new bounds.

11. The system of claim 10 , wherein the one or more new objectives comprises an all-zero objective.

12. The system of claim 10 , wherein the one or more new objectives comprises a randomly-selected objective.

13. The system of claim 10 , wherein determining the one or more objectives of the sub-MILP comprises modifying one of the identified objectives.

14. The system of claim 10 , wherein generating cuts comprises generating at least a cut that cuts multiple LPs.

15. The system of claim

Assignees

• Sas Inst Inc

Inventors

• Narisetty Amar K
• Christophel Philipp M
• Xu Yan

Classifications

• G06N5/01 Primary

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06F17/11 Primary

  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 title

• G06N99/005 Primary

  Physics · mapped topic

• G06N20/00

  Machine learning · CPC title