New theory proves optimal data-driven multipliers for integer programming

A new paper accepted to ICML 2026 tackles the open theoretical question of learning Lagrangian multipliers for large-scale Mixed Integer Linear Programming (MILP). MILP problems like vehicle routing and unit commitment are prevalent in logistics and energy planning. Lagrangian Relaxation (LR) is a classic technique that relaxes coupling constraints to enable parallel subproblem solving and tighter dual bounds, but finding good multipliers traditionally requires manual tuning. Recent empirical work has used machine learning to predict these multipliers, yet a theoretical foundation was lacking.

The authors provide four key contributions. First, they derive a generalization bound of O(s^{1.5}/√N), where s is the number of coupling constraints and N is the training sample size. Second, they prove a minimax lower bound of Ω(s/√N), showing that a linear dependency on constraints is unavoidable. Third, they close this gap by proving that Stochastic Gradient Ascent (SGA) with averaging achieves the minimax optimal rate Θ(s/√N). Finally, they extend the framework to a learning-to-warm-start setting, proving a faster, minimax-optimal rate of Θ(s/N), establishing a theoretical advantage over direct multiplier prediction. These results provide rigorous guarantees that data-driven LR can improve branch-and-bound pruning efficiency across diverse problem distributions.