Mixed-Integer Linear Programming

Also known as MILP

Mixed-integer linear programming combines continuous quantities with integer or binary choices to model problems such as scheduling, routing, resource allocation, and power-system operations. Exact solvers rely on branch-and-bound, cutting planes, presolve, and decomposition methods such as Benders decomposition to find solutions and certify their quality. Current work also uses machine learning to guide branching, warm-start solvers, and predict useful decisions, with learned guidance increasingly combined with rather than substituted for exact optimization. The central challenge is making large instances faster to solve without sacrificing feasibility, reliable performance across problem types, or certificates of solution quality.

Latest papers

50 papers13 papers in the last four weeks, against 2 the four weeks before. 0.1% of all new papers.

Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming
May 18, 2026Tung Quoc Le, Anh Tuan Nguyen, Viet Anh NguyenMixed-Integer Linear Programming Learning to Optimize
Université Grenoble Alpes, LJK, CNRS, Grenoble INP, 38000 Grenoble, France · Carnegie Mellon University, Machine Learning Department · Chinese University of Hong Kong, Department of Systems Engineering and Engineering Management.
LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs
May 11, 2026Zhinan Hou, Xingchen Li, Yankai Zhang +2Branch and Bound Mixed-Integer Linear Programming
Department of Automation, BNRist, Tsinghua University, Beijing, China.
Agentic MIP Research: Accelerated Constraint Handler Generation
May 9, 2026Liding Xu, Yugeng Zhou, Sebastian PokuttaMixed-Integer Linear Programming Constraint Propagation
Zuse Institute Berlin, Berlin, Germany. · Independent Researcher. · Zuse Institute Berlin +1
Optimal Counterfactual Search in Tree Ensembles: A Study Across Modeling and Solution Paradigms
May 7, 2026Awa Khouna, Youssouf Emine, Julien Ferry +1Counterfactual Explanations Mixed-Integer Linear Programming
Polytechnique Montréal · Ivey Business School
Relaxation-Informed Training of Neural Network Surrogate Models
Apr 24, 2026Calvin TsayNeural Surrogate Modeling Mixed-Integer Linear Programming
Department of Computing, Imperial College London, South Kensington, SW7 2AZ, United Kingdom.
A Multi-Stage Warm-Start Deep Learning Framework for Unit Commitment
Apr 23, 2026Muhy Eddin Za'ter, Anna Van Boven, Bri-Mathias Hodge +1Mixed-Integer Linear Programming Power Systems
University of Colorado Boulder Boulder, CO, USA
Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements
Apr 13, 2026Xiang Meng, Andrés Gómez, Rahul MazumderRobust Regression Robust Statistics
MIT Operations Research Center · USC Daniel J. Epstein Department of Industrial and Systems Engineering · MIT Sloan School of Management, Operations Research Center
Structure-Aware Commitment Reduction for Network-Constrained Unit Commitment with Solver-Preserving Guarantees
Apr 3, 2026Guangwen Wang, Jiaqi Wu, Yang Weng +1Power Systems Mixed-Integer Linear Programming
School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, AZ · Department of Electrical and Computer Engineering, University of Washington, Seattle, WA
Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching
Mar 31, 2026Selin Bayramoğlu, George L Nemhauser, Nikolaos V SahinidisLearning to Optimize Branch and Bound
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology · School of Chemical & Biomolecular Engineering, Georgia Institute of Technology
SRG: Score-based Relaxation-guided Generation for Mixed Integer Linear Programming
Mar 25, 2026Ruobing Wang, Xin Li, Yujie Fang +1Mixed-Integer Linear Programming Score-Based Generative Modeling
Beijing Institute of Technology, Beijing, China · University of the Sunshine Coast, Australia
Position Paper: Post-Solve Robustness in Decision Engines: Feasible Regions and Smoothness Under Perturbations
Mar 25, 2026Yi-Xiang HuAlgorithmic Stability Mixed-Integer Linear Programming
University of Science and Technology of China, Hefei, China
Scalable Inspection Planning via Flow-based Mixed Integer Linear Programming
Mar 17, 2026Adir Morgan, Kiril Solovey, Oren SalzmanRobotic Inspection Combinatorial Optimization
Technion–Israel Institute of Technology, Haifa, Israel
Mixed Integer Goal Programming for Personalized Meal Optimization with User-Defined Serving Granularity
Mar 12, 2026Francisco Aguilera MorenoMixed-Integer Linear Programming
A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention
Jan 8, 2026Peixin Huang, Yaoxin Wu, Yining Ma +3Graph Neural Networks Mixed-Integer Linear Programming
Shenzhen Research Institute, Shandong University, China
Machine Learning Guided Optimal Transmission Switching to Mitigate Wildfire Ignition Risk
Oct 29, 2025Weimin Huang, Ryan Piansky, Bistra Dilkina +1Mixed-Integer Linear Programming Learning to Optimize
Department of Computer Science University of Southern California Los Angeles, CA, USA · School of Electrical and Computer Engineering Georgia Institute of Technology Atlanta, GA, USA
Inverse Mixed-Integer Programming: Learning Constraints then Objective Functions
Oct 6, 2025Akira KitaokaMixed-Integer Linear Programming Learning to Optimize
LLM-Guided Evolution of Symbolic Acceleration Inequality Families for MILP
Aug 16, 2025Milad Yazdani, Mahdi Mostajabdaveh, Samin Aref +1Mixed-Integer Linear Programming Integer Linear Programming
Department of Electrical and Computer Engineering, University of British Columbia, Vancouver, BC, Canada · Huawei Technologies Canada, Burnaby, BC, Canada · Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, ON, Canada
OptiMUS-0.3: Using Large Language Models to Model and Solve Optimization Problems at Scale
Jul 29, 2024Ali AhmadiTeshnizi, Wenzhi Gao, Herman Brunborg +3Mixed-Integer Linear Programming Large Language Model-Guided Optimization
a School of Management Science and Engineering, Stanford University, Stanford, California 94305 · b Institute for Computational and Mathematical Engineering, Stanford University, Stanford, California 94305
Distributionally Robust Regularization of Sparse Integer Programming Trained Learning Models
Nov 3, 2023Sanjeeb Dash, Soumyadip Ghosh, Joao Goncalves +1Rule-Based Classification Interpretable ML
IBM Research, Yorktown Heights, NY 10598
Efficient Cross-Validation for Sparse Linear Regression
Jun 26, 2023Ryan Cory-Wright, Andrés GómezModel Selection Cross-Validation
Department of Analytics, Marketing and Operations, Imperial Business School, London, UK · Department of Industrial and Systems Engineering, Viterbi School of Engineering, University of Southern California, CA

May 18, 2026J/K move · Enter open · S save

Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming

Tung Quoc Le, Anh Tuan Nguyen, Viet Anh Nguyen

Université Grenoble Alpes, LJK, CNRS, Grenoble INP, 38000 Grenoble, France · Carnegie Mellon University, Machine Learning Department · Chinese University of Hong Kong, Department of Systems Engineering and Engineering Management.

Mixed-Integer Linear Programming Learning to Optimize Constrained Optimization Linear Programming Learning-Augmented Algorithms

Open paper AskPDF arXiv

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. 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

Ω(s/\sqrt{N})

, proving that a linear dependency is unavoidable. Third, we constructively close this theoretical gap by proving that Stochastic Gradient Ascent (SGA) with averaging achieves the minimax optimal rate

Θ(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)

and establishing a theoretical advantage over direct multiplier prediction.