AI RESEARCH
Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming
arXiv CS.LG
•
ArXi:2605.19052v1 Announce Type: cross Lagrangian Relaxation (LR) is a powerful technique for solving large-scale Mixed Integer Linear Programming (MILP), 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.