Efficiently Solving Repeated Integer Linear Programming Problems by Learning Solutions of Similar Linear Programming Problems using Boosting Trees

摘要

It is challenging to obtain online solutions of large-scale integer linear programming (ILP) problems that occur frequently in slightly different forms during planning for autonomous systems. We refer to such ILP problems as repeated ILP problems. The branch-and-bound (BAB) algorithm is commonly used to solve ILP problems, and a significant amount of computation time is expended in solving numerous relaxed linear programming (LP) problems at the nodes of the BAB trees. We observe that the relaxed LP problems, both within a particular BAB tree and across multiple trees for repeated ILP problems, are similar to each other in the sense that they contain almost the same number of constraints, similar objective function and constraint coefficients, and an identical number of decision variables. We present a boosting tree-based regression technique for learning a set of functions that map the objective function and the constraints to the decision variables of such a system of similar LP problems; this enables us to efficiently infer approximately optimal solutions of the repeated ILP problems. We provide theoretical performance guarantees on the predicted values and demonstrate the effectiveness of the algorithm in four representative domains involving a library of benchmark ILP problems, aircraft carrier deck scheduling, vehicle routing, and vehicle control.