Learning-Based Hierarchical Approach for Fast Mixed-Integer Optimization

Authors

Stefan Clarke, Bartolomeo Stellato

Categories

Abstract

We propose a hierarchical architecture for efficiently computing high-quality solutions to structured mixed-integer programs (MIPs). To reduce computational effort, our approach decouples the original problem into a higher level problem and a lower level problem, both of smaller size. We solve both problems sequentially, where decisions of the higher level problem become parameters of the constraints of the lower level problem. We formulate this learning task as a convex optimization problem using decision-focused learning techniques and solve it by differentiating through the higher and the lower level problems in our architecture. To ensure robustness, we derive out-of-sample performance guarantees using conformal prediction. Numerical experiments in facility location, knapsack problems, and vehicle routing problems demonstrate that our approach significantly reduces computation time while maintaining feasibility and high solution quality compared to state-of-the-art solvers.