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

摘要

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.

主权项

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