Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming

Lagrangian Relaxation (LR) is a powerful technique for solving large-scale mixed-integer linear programs, particularly those with decomposable structures, such as vehicle routing or unit commitment problems. By relaxing the coupling constraints, LR enables parallel subproblem solving and often yields tighter dual bounds than standard linear programming relaxations, which is crucial for efficient branch-and-bound pruning. While recent empirical work has shown promising results using machine learning to predict these multipliers, a theoretical understanding of such methods remains an open question. In this work, we bridge this gap by analyzing the problem of learning LR through the lens of data-driven algorithm design, i.e., a statistical learning problem over a distribution of problem instances. Our contributions are as follows: first, we derive a generalization bound of $\mathcal{O}(s^{1.5}/\sqrt{N})$ for the learned multipliers, where $s$ is the number of coupling constraints and $N$ is the sample size. Second, we provide a minimax lower-bound of $\Omega(s/\sqrt{N})$, proving that a linear dependency is unavoidable. Third, we constructively close this theoretical gap by proving that stochastic gradient ascent with averaging achieves the minimax optimal rate $\Theta(s/\sqrt{N})$. Finally, we extend our framework to the learning-to-warm-start setting, proving that it achieves a fast, minimax-optimal rate of $\Theta(s/N)$ and establishing a theoretical advantage over direct multiplier prediction.

Mixed-integer linear programming is a widely used optimization framework for difficult decision-making problems in logistics, energy, finance, and other industrial domains. These problems are often very hard to solve, exactly because they combine continuous decisions with discrete yes-or-no choices. A classical technique called Lagrangian relaxation can make such problems easier by relaxing a small set of difficult linking constraints, splitting the original problem into simpler subproblems, and producing strong bounds that help optimization solvers run faster. The effectiveness of Lagrangian relaxation depends heavily on choosing good multipliers for the relaxed constraints. Recent machine learning methods have tried to predict these multipliers from previously solved problem instances, but until now, there has been little theoretical understanding of when this approach should work. This paper develops a statistical learning framework for data-driven Lagrangian relaxation. We prove how many training instances are needed to learn useful multipliers, show that some dependence on the number of relaxed constraints is unavoidable, and identify an algorithm that achieves the best possible learning rate. We also study a warm-starting approach, where learning is used to initialize a classical solver rather than replace it, and prove that this can be more sample-efficient.