Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming
Tung Quoc Le, Anh Tuan Nguyen, Viet Anh Nguyen · 2026
Read Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming by Tung Quoc Le, Anh Tuan Nguyen, Viet Anh Nguyen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-19052.txt.
Introduction
Tung Quoc Le, Anh Tuan Nguyen, and Viet Anh Nguyen give a theory for learning Lagrangian relaxation multipliers for mixed-integer linear programs from data. They derive a generalisation bound for the learned multipliers. They prove a matching lower bound. It shows a linear link to the number of coupling constraints cannot be avoided. They also show averaged stochastic gradient ascent attains the optimal rate. Finally, they extend the work to warm-start learning, proving a faster optimal rate and an edge over predicting multipliers directly.
Catalog record
| CREATOR | Tung Quoc Le, Anh Tuan Nguyen, Viet Anh Nguyen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77646 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.19052
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming Tung Quoc Le, Anh Tuan Nguyen, Viet Anh Nguyen Abstract 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 𝒪 ( s 1.5 / N ) \mathcal{O}(s^{1.5}/\sqrt{N}) for the learned multipliers, where s s is the number of coupling constraints and N N is the sample size. Second, we provide a minimax lower-bound of Ω ( s / N ) \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 Θ ( s / N ) \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 Θ ( s / N ) \Theta(s/N) and establishing a theoretical advantage over direct multiplier prediction. 1 Introduction Mixed Integer Linear Programming (MILP) ( 17 ; 43 ) is one of the most fundamental problems in optimization literature that plays a critical role in many industrial areas, including supply chains and logistics ( 26 ) , energy and power systems ( 14 ) , and finance ( 21 ) , among others. While modern solvers (e.g., branch-and-cut ( 31 ) ) have made tremendous advances, solving large-scale MILP instances to optimality remains a computationally intensive task due to the combinatorial explosion of the search tree. This necessitates advanced decomposition techniques to accelerate the solving process. For many real-world MILP problems, including the Vehicle Routing Problem (VRP) ( 39 ) and the Unit Commitment Problem ( 37 ) , the complexity arises from a small set of coupling constraints (e.g., shared resources or capacity limits) linking together otherwise independent sub-problems. Lagrangian relaxation (LR) ( 19 ) addresses this issue by dualizing these coupling constraints into the objective function. Concretely, let P=(c,A,b,C,d) be a MILP problem instance of the form \textup{OPT}(P)\triangleq\left\{\begin{array}[]{cl}\min&c^{\top}x\\ \text{s.t.}&x\in\mathbb{R}_{+}^{m}\times\{0,1\}^{p},~Ax\geq b,~Cx\geq d,\end{array}\right. where Ax\geq b represents the coupling constraints. Using \pi\geq 0 as the dual variable, LR dualizes the coupling constraints into the objective function as follows u(\pi,P)\triangleq\left\{\begin{array}[]{cl}\min&c^{\top}x+\pi^{\top}(b-Ax)\\ \textup{s.t.}&x\in\mathbb{R}^{m}_{+}\times\{0,1\}^{p},~Cx\geq d.\end{array}\right. LR offers two important advantages for MILP solvers. First, it decomposes the problem into smaller, often tractable subproblems that can be solved in parallel; see Appendix A for an example of such decomposition in VRP. Second, because u(\pi,P)\leq\textup{OPT}(P) and because these subproblems retain their integrity constraints, LR yields a better, often significantly tighter, objective lower-bound than the continuous relaxation (CR) ( 20 ) . These tighter bounds are instrumental in pruning the branch-and-bound tree and massively accelerating exact MILP solvers. However, the efficiency of LR relies heavily on how fast we can identify the optimal values of the Lagrangian multipliers \pi . Given a problem instance P , finding the optimal multipliers that maximize the dual bound, and thus provide the best pruning power, is a non-smooth concave optimization problem. Consequently, the computation cost of finding good multipliers may sometimes outweigh the benefits of a tighter bound. In many practical settings, the optimization problem instances P are not isolated but appear as related samples coming from an application-specific problem distribution \mathcal{D} . For example, in the VRP case, we may observe daily routing demands on the same road network. Based on this fact, recent empirical works ( 18 ) proposed learning the Lagrangian multipliers \pi^{*}(\mathcal{D}) for such problem distribution based on the past problem instances. Given a new test problem instance arriving from the same problem distribution, the learned \pi^{*}(\mathcal{D}) can be used to either (1) warm-start the sub-gradient method and drastically reduce the number of iterations required to reach convergence, or (2) approximate the dual bound directly without further re-calculation. However, despite some promising empirical results, this learning-augmented approach currently lacks a rigorous theoretical foundation. Contributions. In this work, we lay the theoretical foundation for Lagrange multiplier learning by analyzing LR through the lens of data-driven algorithm design ( 22 ; 9 ) . Concretely, we formalize learning the Lagrangian multipliers as a statistical learning problem and provide the first rigorous sample-complexity guarantee for this task. Our contributions are fourfold: 1. First, we derive a generalization guarantee upper-bound of \mathcal{O}(s^{1.5}/\sqrt{N}) for learning the Lagrangian multipliers that maximize the dual objective, where s is the number of coupling constraints, and N is the number of training problem instances. 2. Second, we establish a generalization minimax lower-bound of \Omega(s/\sqrt{N}) , demonstrating that a linear dependence on the number of coupling constraints is unavoidable. 3. Third, we constructively close the resulting \mathcal{O}(\sqrt{s}) gap by analyzing the Stochastic Gradient Ascent (SGA) with the averaging algorithm, proving that it achieves the minimax optimal rate of \mathcal{O}(s/\sqrt{N}) . 4. Finally, we extend our analysis to the learning-to-warm-start setting. We prove that this formulation admits a fast, minimax-optimal generalization rate of \Theta(s/N) , establishing a provable difference in sample complexity compared to direct multiplier prediction. Technical challenges and overview. To establish the upper and lower bounds for generalization guarantees, we analyze the function class \mathcal{U}=\{u_{\pi}:\mathcal{P}\rightarrow[-H,H]\mid\pi\in\mathbb{R}^{s}_{+}\} , where u_{\pi}(P)\triangleq u(\pi,P) and H\in\mathbb{R}_{+} is a range bound of the function class. Unlike standard problems in learning theory literature, the structure of the function u_{\pi}(P) is more complicated because u_{\pi}(P) is inherently defined by an optimization problem. To overcome this challenge, we take the dual view perspective from data-driven algorithm design literature ( 9 ) : we will analyze the function u_{P}(\pi)\triangleq u(\pi,P) acquired by fixing the MILP problem instance P and treating the Lagrangian multipliers \pi as variables. In doing so, we can exploit the favorable structure of the function class in Section 5.1 and then establish an upper-bound for the generalization guarantee for \mathcal{U} . For the lower bound, we employ a standard reduction in theoretical statistics from estimation to testing, using Fano’s method from Theorem 3.3 . To do this, we design a family of hard problem distributions distinguished by specific perturbations, controlled by a binary vector v\in\{0,1\}^{s} , in their objective coefficient c . By constructing a hypercube packing of the controlling vector v , we induce a family of hard problem distributions \mathcal{D}_{v}\in\Delta(\mathcal{P}) that remain statistically hard to distinguish while their optimal multipliers \pi^{*}(\mathcal{D}_{v}) remain geometrically separated, thereby establishing an information-theoretic lower-bound for the problem of data-driven Lagrangian relaxation learning. Outline. We structure our paper as follows: Section 2 discuss the existing literature, while Section 3 collects key technical preliminaries. In Section 4 , we present the setup of the Lagrangian relaxation learning framework. We present our main results on generalization guarantees, the minimax lower bound, and the optimal SGA algorithm in