Mixed-Integer Linear Programming

Also known as MILP

Ask about this topic

Overview

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

CardsList

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

May 18, 2026

Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming

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 O(s1.5/N)\mathcal{O}(s^{1.5}/\sqrt{N}) for the learned multipliers, where ss is the number of coupling constraints and NN is the sample size. Second, we provide a minimax lower-bound of Ω(s/N)Ω(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/N)Θ(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)Θ(s/N) and establishing a theoretical advantage over direct multiplier prediction.

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 ProgrammingLearning to OptimizeConstrained OptimizationLinear ProgrammingLearning-Augmented Algorithms
AskPDF
May 11, 2026

LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs

Efficient branching policies are essential for accelerating Mixed Integer Linear Programming (MILP) solvers. Their design has long relied on hand-crafted heuristics, and now machine learning has emerged as a promising paradigm to automate this process. However, existing learning-based methods are often hindered by their dependence on expensive expert demonstrations and the gap between training objectives and the solver's end-to-end performance. In this work, we propose LLM4Branch, a novel framework that leverages Large Language Models (LLMs) to automate the discovery of efficient branching policies. Specifically, the discovered policy is an executable program with a program skeleton generated by the LLM and a parameter vector, which is optimized via a zeroth-order method over a few instances with their end-to-end performance feedback. Extensive experiments on standard MILP benchmarks demonstrate that LLM4Branch establishes a new state-of-the-art among CPU-based methods and achieves performance competitive with advanced GPU-based models. Codes are available at https://github.com/hzn18/LLM4Branch.

Zhinan Hou, Xingchen Li, Yankai Zhang +2

Department of Automation, BNRist, Tsinghua University, Beijing, China.

Branch and BoundMixed-Integer Linear ProgrammingLarge Language Model-Guided OptimizationLearning to OptimizeLLM-Based Program SynthesisInteger Linear Programming
AskPDF
May 9, 2026

Agentic MIP Research: Accelerated Constraint Handler Generation

Mixed-integer programming (MIP) research is both mathematically sophisticated and engineering-intensive: testing an algorithmic hypothesis within a branch-and-cut solver requires substantial implementation, debugging, tuning, and large-scale benchmarking. We propose an agentic MIP research framework that shortens this feedback loop by embedding LLM agents into a solver-aware harness for generating, verifying, and evaluating plugins for the open-source solver SCIP. Propagation methods play a central role in accelerating MIP solving by exploiting global constraints. We instantiate our framework on the semantic lifting of MIP formulations into global constraints and the automatic construction of propagation-only SCIP constraint handlers. On the MIPLIB 2017 benchmark set, the framework successfully recovers global constraint structures from constraint programming and generates executable constraint detectors and propagation-only constraint handlers. Furthermore, the framework naturally extends to in-context learning within a sandboxed environment, enabling agents not only to tune and debug generated constraint handlers on real instances, but also to explore global constraint patterns in MIP problems and discover novel propagation strategies not yet implemented in SCIP. This framework allows us to systematically distinguish meaningful algorithmic improvements from low-value or overly costly candidates: the novel propagation methods successfully solved five additional instances within the explored benchmark. Overall, this framework demonstrates that LLM agents can autonomously navigate the complex MIP research loop, paving the way for a more automated solver development process.

Liding Xu, Yugeng Zhou, Sebastian Pokutta

Zuse Institute Berlin, Berlin, Germany. · Independent Researcher. · Zuse Institute Berlin +1

Mixed-Integer Linear ProgrammingConstraint PropagationLLM-Based Program SynthesisConstraint SatisfactionAutonomous Research Agents
AskPDF
May 7, 2026

Optimal Counterfactual Search in Tree Ensembles: A Study Across Modeling and Solution Paradigms

Trust in counterfactual explanations depends critically on whether their recommended changes are truly minimal: suboptimal explanations may vastly overshoot the actual changes needed to alter a decision, and heuristic errors can affect individuals unevenly, giving some users relevant recourse while assigning others unnecessarily costly recommendations. Consequently, we study the problem of computing optimal counterfactual explanations for tree ensembles under plausibility and actionability constraints. This is a combinatorial problem: for a fixed model, counterfactual search boils down to selecting consistent branching decisions and threshold-defined regions under a distance objective. We exploit this structure through CPCF, a constraint programming (CP) formulation in which numerical features are encoded as interval domains induced by split thresholds, while discrete features retain native finite-domain representations. This yields a compact finite-domain formulation that supports multiple distance objectives without continuous split-boundary search. We then place CPCF in a broader comparison across mathematical programming paradigms: we extend a maximum Boolean satisfiability (MaxSAT) formulation, originally designed for hard-voting random forests, to soft-voting ensembles, and compare against the current state-of-the-art mixed-integer linear programming (MILP) optimal approach. Across ten datasets and three types of tree ensembles, we analyze scalability, anytime performance, and sensitivity to distance metrics. We observe that CP achieves the best overall performance. More importantly, our results identify regimes in which the specific strengths of each paradigm make it best suited: CP is most versatile overall, MaxSAT handles hard-voting ensembles particularly well, and MILP remains competitive in amortized inference settings with a moderate number of split levels.

Awa Khouna, Youssouf Emine, Julien Ferry +1

Polytechnique Montréal · Ivey Business School

Counterfactual ExplanationsMixed-Integer Linear ProgrammingCombinatorial OptimizationMaximum SatisfiabilityConstraint Programming
AskPDF
Apr 24, 2026

Relaxation-Informed Training of Neural Network Surrogate Models

ReLU neural networks trained as surrogate models can be embedded exactly in mixed-integer linear programs (MILPs), enabling global optimization over the learned function. The tractability of the resulting MILP depends on structural properties of the network, i.e., the number of binary variables in associated formulations and the tightness of the continuous LP relaxation. These properties are determined during training, yet standard training objectives (prediction loss with classical weight regularization) offer no mechanism to directly control them. This work studies training regularizers that directly target downstream MILP tractability. Specifically, we propose simple bound-based regularizers that penalize the big-M constants of MILP formulations and/or the number of unstable neurons. Moreover, we introduce an LP relaxation gap regularizer that explicitly penalizes the per-sample gap of the continuous relaxation at training points. We derive its associated gradient and provide an implementation from LP dual variables without custom automatic differentiation tools. We show that combining the above regularizers can approximate the full total derivative of the LP gap with respect to the network parameters, capturing both direct and indirect sensitivities. Experiments on non-convex benchmark functions and a two-stage stochastic programming problem with quantile neural network surrogates demonstrate that the proposed regularizers can reduce MILP solve times by up to four orders of magnitude relative to an unregularized baseline, while maintaining competitive surrogate model accuracy.

Calvin Tsay

Department of Computing, Imperial College London, South Kensington, SW7 2AZ, United Kingdom.

Neural Surrogate ModelingMixed-Integer Linear ProgrammingNeural Network OptimizationConstrained OptimizationInteger Linear Programming
AskPDF
Apr 23, 2026

A Multi-Stage Warm-Start Deep Learning Framework for Unit Commitment

Maintaining instantaneous balance between electricity supply and demand is critical for reliability and grid instability. System operators achieve this through solving the task of Unit Commitment (UC),ca high dimensional large-scale Mixed-integer Linear Programming (MILP) problem that is strictly and heavily governed by the grid physical constraints. As grid integrate variable renewable sources, and new technologies such as long duration storage in the grid, UC must be optimally solved for multi-day horizons and potentially with greater frequency. Therefore, traditional MILP solvers increasingly struggle to compute solutions within these tightening operational time limits. To bypass these computational bottlenecks, this paper proposes a novel framework utilizing a transformer-based architecture to predict generator commitment schedules over a 72-hour horizon. Also, because raw predictions in highly dimensional spaces often yield physically infeasible results, the pipeline integrates the self-attention network with deterministic post-processing heuristics that systematically enforce minimum up/down times and minimize excess capacity. Finally, these refined predictions are utilized as a warm start for a downstream MILP solver, while employing a confidence-based variable fixation strategy to drastically reduce the combinatorial search space. Validated on a single-bus test system, the complete multi-stage pipeline achieves 100% feasibility and significantly accelerates computation times. Notably, in approximately 20% of test instances, the proposed model reached a feasible operational schedule with a lower overall system cost than relying solely on the solver.

Muhy Eddin Za'ter, Anna Van Boven, Bri-Mathias Hodge +1

University of Colorado Boulder Boulder, CO, USA

Mixed-Integer Linear ProgrammingPower Systems
AskPDF
Apr 13, 2026

Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements

We study computational aspects of a key problem in robust statistics -- the penalized least trimmed squares (LTS) regression problem, a robust estimator that mitigates the influence of outliers in data by capping residuals with large magnitudes. Although statistically attractive, penalized LTS is NP-hard, and existing mixed-integer optimization (MIO) formulations scale poorly due to weak relaxations and exponential worst-case complexity in the number of observations. We propose a new MIO formulation that embeds hyperplane arrangement logic into a perspective reformulation, explicitly enforcing structural properties of optimal solutions. We show that, if the number of features is fixed, the resulting branch-and-bound tree is of polynomial size in the sample size. Moreover, we develop a tailored branch-and-bound algorithm that uses first-order methods with dual bounds to solve node relaxations efficiently. Computational experiments on synthetic and real datasets demonstrate substantial improvements over existing MIO approaches: on synthetic instances with 5000 samples and 20 features, our tailored solver reaches a 1% gap in 1 minute while competing approaches fail to do so within one hour. These gains enable exact robust regression at significantly larger sample sizes in low-dimensional settings.

Xiang Meng, Andrés Gómez, Rahul Mazumder

MIT Operations Research Center · USC Daniel J. Epstein Department of Industrial and Systems Engineering · MIT Sloan School of Management, Operations Research Center

Robust RegressionRobust StatisticsBranch and BoundMixed-Integer Linear Programming
AskPDF
Apr 3, 2026

Structure-Aware Commitment Reduction for Network-Constrained Unit Commitment with Solver-Preserving Guarantees

The growing number of individual generating units, hybrid resources, and security constraints has significantly increased the computational burden of network-constrained unit commitment (UC), where most solution time is spent exploring branch-and-bound trees over unit-hour binary variables. To reduce this combinatorial burden, recent approaches have explored learning-based guidance to assist commitment decisions. However, directly using tools such as large language models (LLMs) to predict full commitment schedules is unreliable, as infeasible or inconsistent binary decisions can violate inter-temporal constraints and degrade economic optimality. This paper proposes a solver-compatible dimensionality reduction framework for UC that exploits structural regularities in commitment decisions. Instead of generating complete schedules, the framework identifies a sparse subset of structurally stable commitment binaries to fix prior to optimization. One implementation uses an LLM to select these variables. The LLM does not replace the optimization process but provides partial variable restriction, while all constraints and remaining decisions are handled by the original MILP solver, which continues to enforce network, ramping, reserve, and security constraints. We formally show that the masked problem defines a reduced feasible region of the original UC model, thereby preserving feasibility and enabling solver-certified optimality within the restricted space. Experiments on IEEE 57-bus, RTS 73-bus, IEEE 118-bus, and augmented large-scale cases, including security-constrained variants, demonstrate consistent reductions in branch-and-bound nodes and solution time, achieving order-of-magnitude speedups on high-complexity instances while maintaining near-optimal objective values.

Guangwen Wang, Jiaqi Wu, Yang Weng +1

School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, AZ · Department of Electrical and Computer Engineering, University of Washington, Seattle, WA

Power SystemsMixed-Integer Linear ProgrammingLarge Language Model-Guided Optimization
AskPDF
Mar 31, 2026

Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching

Machine learning is increasingly used to improve decisions within branch-and-bound algorithms for mixed-integer programming. Many existing approaches rely on deep learning, which often requires very large training datasets and substantial computational resources for both training and deployment, typically with GPU parallelization. In this work, we take a different path by developing interpretable models that are simple but effective. We focus on approximating strong branching (SB) scores, a highly effective yet computationally expensive branching rule. Using sparse learning methods, we build models with fewer than 4% of the parameters of a state-of-the-art graph neural network (GNN) while achieving competitive accuracy. Relative to SCIP's built-in branching rules and the GNN-based model, our CPU-only models are faster than the default solver and the GPU-accelerated GNN. The models are simple to train and deploy, and they remain effective with small training sets, which makes them practical in low-resource settings. Extensive experiments across diverse problem classes demonstrate the efficiency of this approach.

Selin Bayramoğlu, George L Nemhauser, Nikolaos V Sahinidis

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology · School of Chemical & Biomolecular Engineering, Georgia Institute of Technology

Learning to OptimizeBranch and BoundMixed-Integer Linear Programming
AskPDF
Mar 25, 2026

SRG: Score-based Relaxation-guided Generation for Mixed Integer Linear Programming

We propose Score-based Relaxation-guided Generation (SRG), a generative framework based on an approximate formulation of relaxation-guided stochastic differential equations (SDEs) for mixed-integer linear programming. SRG employs a Transformer-based score network that incorporates feasibility and optimality signals into score modeling, encouraging the learned generative model to place more probability mass on feasible, high-quality regions of the solution space. At inference time, SRG directly samples diverse candidate solutions from the learned score model without requiring any additional guidance module. These candidates are then used to construct compact trust-region subproblems for standard MILP solvers. Across multiple public benchmarks, SRG matches or improves upon the solution quality of the strongest learning-based baselines, with particularly strong gains in challenging candidate-generation settings. Moreover, SRG shows promising zero-shot transferability to unseen cross-scale and cross-problem instances, improving solver objectives and reducing search time in several cases through higher-quality initial candidates and compact trust-region search.

Ruobing Wang, Xin Li, Yujie Fang +1

Beijing Institute of Technology, Beijing, China · University of the Sunshine Coast, Australia

Mixed-Integer Linear ProgrammingScore-Based Generative ModelingConstrained Generative Modeling
AskPDF
Mar 25, 2026

Position Paper: Post-Solve Robustness in Decision Engines: Feasible Regions and Smoothness Under Perturbations

Mixed-Integer Linear Programming (MILP) decision engines routinely output nominally optimal plans for high-stakes industrial systems. Yet deployment rarely matches solve-time assumptions: small perturbations in costs, demands, or resource availability can invalidate feasibility or trigger discontinuous shifts to qualitatively different solutions. We argue that this post-solve robustness gap is a missing layer in today's optimization pipelines and a missing evaluation dimension for learning-enabled decision systems. Rather than replacing robust optimization or stochastic programming, the proposed layer audits a solved incumbent and returns solver-backed evidence about how far that solution can be trusted. We formalize two central objects: (i) an εε-near-optimal feasible neighborhood in parameter space, capturing when an incumbent remains feasible and near-optimal under perturbations, and (ii) solution smoothness in decision space, capturing whether nearby alternatives with small combinatorial edits remain competitive. We then synthesize the most relevant partial answers from sensitivity and stability analysis, robust optimization, neighborhood search, adversarial testing, and learning-based enhancements, and articulate an agenda for a unified post-solve robustness layer. Concretely, we call for certified inner approximations around the incumbent, probabilistic robustness estimation with calibrated uncertainty, adversarial robustness margins, and learning-based prediction and explanation aligned with solver-backed verification. We conclude with a compact reporting template and evaluation protocol that would make robustness a first-class output of decision engines.

Yi-Xiang Hu

University of Science and Technology of China, Hefei, China

Algorithmic StabilityMixed-Integer Linear ProgrammingRobust Optimization
AskPDF
Mar 17, 2026

Scalable Inspection Planning via Flow-based Mixed Integer Linear Programming

Inspection planning is concerned with computing the shortest robot path to inspect a given set of points of interest (POIs) using the robot's sensors. This problem arises in a wide range of applications from manufacturing to medical robotics. To alleviate the problem's complexity, recent methods rely on sampling-based methods to obtain a more manageable (discrete) graph inspection planning (GIP) problem. Unfortunately, GIP still remains highly difficult to solve at scale as it requires simultaneously satisfying POI-coverage and path-connectivity constraints, giving rise to a challenging optimization problem, particularly at scales encountered in real-world scenarios. In this work, we present highly scalable Mixed Integer Linear Programming (MILP) solutions for GIP that significantly advance the state-of-the-art in both runtime and solution quality. Our key insight is a reformulation of the problem's core constraints as a network flow, which enables effective MILP models and a specialized Branch-and-Cut solver that exploits the combinatorial structure of flows. We evaluate our approach on medical and infrastructure benchmarks alongside large-scale synthetic instances. Across all scenarios, our method produces substantially tighter lower bounds than existing formulations, reducing optimality gaps by 30-50% on large instances. Furthermore, our solver demonstrates unprecedented scalability: it provides non-trivial solutions for problems with up to 15,000 vertices and thousands of POIs, where prior state-of-the-art methods typically exhaust memory or fail to provide any meaningful optimality guarantees.

Adir Morgan, Kiril Solovey, Oren Salzman

Technion–Israel Institute of Technology, Haifa, Israel

Robotic InspectionCombinatorial OptimizationMixed-Integer Linear Programming
AskPDF
Mar 12, 2026

Mixed Integer Goal Programming for Personalized Meal Optimization with User-Defined Serving Granularity

Determining what to eat to satisfy nutritional requirements is one of the oldest optimization problems in operations research, yet existing formulations have two persistent limitations: continuous variables produce impractical fractional servings (1.7 eggs, 0.37 bananas), and hard nutrient constraints cause infeasibility when targets conflict. A systematic review of 56 diet optimization papers found that none combine integer programming with goal programming to address both issues. We propose Mixed Integer Goal Programming (MIGP) for personalized meal optimization. The formulation uses integer variables for practical serving counts and goal programming deviations for soft nutrient targets, with inverse-target normalization to balance multi-nutrient optimization. Per-food serving granularity allows natural units (one egg, one tablespoon of oil) without post-hoc rounding. We characterize the integrality gap in the goal programming context and identify a deviation absorption property: GP deviation variables buffer the cost of requiring integer servings, making the gap structurally smaller than in hard-constraint MIP. For meals with 15+ foods, the integer solution matches the continuous optimum in every benchmark instance. A computational evaluation across 810 instances (30 USDA foods, 9 configurations, 3 methods) shows MIGP finds strictly better solutions than GP with post-hoc rounding in 66% of cases (never worse) while maintaining 100% feasibility; hard-constraint IP achieves only 48%. Solve times stay under 100 ms for typical meal sizes using the open-source HiGHS solver. The implementation is available as an open-source Python module integrated into an interactive meal planning application.

Francisco Aguilera Moreno

Mixed-Integer Linear Programming
AskPDF
Jan 8, 2026

A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention

Mixed-integer linear programming (MILP) is a foundational framework for combinatorial optimization across science and engineering, but remains hard to solve at scale due to NP-hardness. Recent learning-based methods typically model MILP instances as variable-constraint bipartite graphs and use Graph Neural Networks (GNNs) for representation learning, yet their locality limits representation power. We propose an attention-driven neural backbone that adopts an element-centric view of variables and constraints, with dual attention performing parallel intra-type self-attention and inter-type cross-attention. Across three representative tasks at the instance, element, and solving-state levels, our model consistently outperforms conventional GNN-based architectures, highlighting attention-based, element-centric modeling as a powerful foundation for learning-enhanced combinatorial optimization.

Peixin Huang, Yaoxin Wu, Yining Ma +3

Shenzhen Research Institute, Shandong University, China

Graph Neural NetworksMixed-Integer Linear ProgrammingLinear ProgrammingNeural Combinatorial OptimizationInteger Linear Programming
AskPDF
Oct 29, 2025

Machine Learning Guided Optimal Transmission Switching to Mitigate Wildfire Ignition Risk

To mitigate acute wildfire ignition risks, utilities de-energize power lines in high-risk areas. The Optimal Power Shutoff (OPS) problem optimizes line energization statuses to manage wildfire ignition risks through de-energizations while reducing load shedding. OPS problems are computationally challenging Mixed-Integer Linear Programs (MILPs) that must be solved rapidly and frequently in operational settings. For a particular power system, OPS instances share a common structure with varying parameters related to wildfire risks, loads, and renewable generation. This motivates the use of Machine Learning (ML) for solving OPS problems by exploiting shared patterns across instances. In this paper, we develop an ML-guided framework that quickly produces high-quality de-energization decisions by extending existing ML-guided MILP solution methods while integrating domain knowledge on the number of energized and de-energized lines. Results on a large-scale realistic California-based synthetic test system show that the proposed ML-guided method produces high-quality solutions faster than traditional optimization methods.

Weimin Huang, Ryan Piansky, Bistra Dilkina +1

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

Mixed-Integer Linear ProgrammingLearning to OptimizePower Systems
AskPDF
Oct 6, 2025

Inverse Mixed-Integer Programming: Learning Constraints then Objective Functions

Data-driven inverse optimization for mixed-integer linear programs (MILPs), which seeks to learn an objective function and constraints consistent with observed decisions, is important for building accurate mathematical models in a variety of domains, including power systems and scheduling. However, to the best of our knowledge, existing data-driven inverse optimization methods primarily focus on learning objective functions under known constraints, and learning both objective functions and constraints from data for MILPs remains largely unexplored. In this paper, we propose a two-stage approach for a class of inverse optimization problems in which the objective is a linear combination of given feature functions and the constraints are parameterized by unknown functions and thresholds. Our method first learns the constraints and then, conditioned on the learned constraints, estimates the objective-function weights. On the theoretical side, we provide finite-sample guarantees for solving the proposed inverse optimization problem. To this end, we develop statistical learning tools for pseudo-metric spaces under sub-Gaussian assumptions and use them to derive a learning-theoretic framework for inverse optimization with both unknown objectives and constraints. On the experimental side, we demonstrate that our method successfully solves inverse optimization problems on scheduling instances formulated as ILPs with up to 100 decision variables.

Akira Kitaoka

Mixed-Integer Linear ProgrammingLearning to OptimizeInverse ProblemsInteger Linear Programming
AskPDF
Aug 16, 2025

LLM-Guided Evolution of Symbolic Acceleration Inequality Families for MILP

Integer programming (IP) is central to many combinatorial optimization tasks but remains challenging due to its NP-hard nature. A practical way to improve IP solvers is to manually design inequality families that exploit problem structure. However, this creative process requires deep expertise and has therefore been difficult to automate. Our proposed framework, Symbolic Acceleration via Generative Evolution (SAGE), automates symbolic discovery of acceleration inequality families at the modeling level. It reasons over a symbolic IP formulation and a natural language description of the problem to discover a reusable set of acceleration inequality families that can be instantiated for each problem instance. These acceleration inequality families are selected through empirical admissibility and impact screening rather than mathematical proofs. SAGE (i) initializes a population of candidate acceleration inequality families via an initializer agent that uses an LLM; (ii) it screens candidates for admissibility on a small development admissibility set for solution feasibility and the separation of the relaxation solution; and (iii) it iteratively refines the population of inequalities through evolutionary crossover and mutation agents. Across seven MILP benchmarks, SAGE reduces optimality gaps by up to 62.1%62.1\% relative to baseline MILP formulations solved with a fixed time budget and reaches target gaps up to 5.51×5.51\times faster according to shifted geometric mean speedup. Comprehensive ablations show its robustness across different LLM backends and across solvers and internal cut settings. Code: https://github.com/milad1378yz/sage

Milad Yazdani, Mahdi Mostajabdaveh, Samin Aref +1

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

Mixed-Integer Linear ProgrammingInteger Linear ProgrammingLarge Language Model-Guided Optimization
AskPDF
Jul 29, 2024

OptiMUS-0.3: Using Large Language Models to Model and Solve Optimization Problems at Scale

Optimization problems are pervasive in sectors from manufacturing and distribution to healthcare. However, most such problems are still solved heuristically by hand rather than optimally by state-of-the-art solvers because the expertise required to formulate and solve these problems limits the widespread adoption of optimization tools and techniques. We introduce a Large Language Model (LLM)-based system designed to formulate and solve (mixed integer) linear programming problems from their natural language descriptions. Our system can develop mathematical models, write and debug solver code, evaluate the generated solutions, and improve efficiency and correctness of its model and code based on these evaluations. OptiMUS is designed as a productivity tool for optimization practitioners who understand the problem domain and can describe it precisely, but seek to accelerate the modeling and implementation workflow. OptiMUS-0.3 utilizes a modular structure to process problems, allowing it to handle problems with long descriptions and complex data without long prompts. Experiments demonstrate that OptiMUS-0.3 outperforms direct-prompting baselines by over 43% on easy and 18% on hard instances. It remains competitive with fine-tuned specialist models on benchmark problems, and outperforms them on real-world case studies (28.6% vs. 0%) where fine-tuned models fail to generalize. Ablation studies show that modular architecture with error correction is central to these gains. A key finding is that system architecture is a stronger driver of performance than model capability. Structured decomposition with targeted error correction enables weaker models to match stronger models under naive prompting, and remains competitive with fine-tuned specialist models without retraining costs.

Ali AhmadiTeshnizi, Wenzhi Gao, Herman Brunborg +3

a School of Management Science and Engineering, Stanford University, Stanford, California 94305 · b Institute for Computational and Mathematical Engineering, Stanford University, Stanford, California 94305

Mixed-Integer Linear ProgrammingLarge Language Model-Guided OptimizationLLM-Based Program SynthesisLinear ProgrammingNatural Language to Optimization ModelingInteger Linear Programming
AskPDF
Nov 3, 2023

Distributionally Robust Regularization of Sparse Integer Programming Trained Learning Models

Building explainable machine learning models is crucial for human users to be able to interpret the proposed statistical relationship obtained from the training data. Mixed-integer optimization formulations are often used to train such models with explicit sparsity constraints, aiming to strike the right trade-off between sparsity and prediction accuracy. Existing methods to find the right choice of sparsity -- e.g., via cross-validation -- are computationally expensive. For convex model training formulations, recent advances in distributionally robust optimization (DRO) provide strong generalization while sidestepping this computational burden. We describe an extension of such regularization via DRO to mixed-integer sparse programs, providing statistical guarantees as a function of an associated sparsity parameter of the formulation. We illustrate the use of this approach in the case of building explainable binary classification models using sets of feature value rules.

Sanjeeb Dash, Soumyadip Ghosh, Joao Goncalves +1

IBM Research, Yorktown Heights, NY 10598

Rule-Based ClassificationInterpretable MLDistributionally Robust OptimizationMixed-Integer Linear Programming
AskPDF
Jun 26, 2023

Efficient Cross-Validation for Sparse Linear Regression

Given a high-dimensional covariate matrix and a response vector, ridge-regularized sparse linear regression selects a subset of features that explains the relationship between covariates and the response in an interpretable manner. To choose hyperparameters that control the sparsity level and amount of regularization, practitioners commonly use k-fold cross-validation. However, cross-validation substantially increases the computational cost of sparse regression as it requires solving many mixed-integer optimization problems (MIOs) for each hyperparameter combination. To address this computational burden, we derive computationally tractable relaxations of the k-fold cross-validation loss, facilitating hyperparameter selection while solving 5050--80%80\% fewer MIOs in practice. Our computational results demonstrate, across eleven real-world UCI datasets, that exact MIO-based cross-validation can be competitive with mature software packages such as glmnet and L0Learn.

Ryan Cory-Wright, Andrés Gómez

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

Model SelectionCross-ValidationMixed-Integer Linear ProgrammingLinear RegressionHyperparameter OptimizationHigh-Dimensional Linear Regression
AskPDF