Linear Programming

Also known as LP

Linear programming represents decisions with linear objectives and constraints, making it a basic tool for allocating scarce resources, scheduling, and modeling uncertain or sequential decisions. Work spans exact algorithms such as simplex, interior-point, and primal-dual methods; duality, relaxations, and network-flow structure also provide bounds, integral solutions, and efficient formulations. For online allocation and stochastic optimization, researchers develop pricing, batching, and re-solving methods with regret guarantees, while newer work learns solver parameters, warm starts, or model formulations from data and uses language-model agents with solver checks. Key challenges include scaling to large or changing instances, obtaining guarantees that survive approximation and distribution shift, and balancing learned speedups with exact feasibility and optimality certification.

Latest papers

26 papers6 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Learning Warm Starts for the Simplex Method from Measured Solver Cost
Oct 14, 2026Felix Parker, Danielle A. Ripsman, Emmett Springer +1Linear Programming Learning to Optimize
Center for Systems Science and Engineering, Johns Hopkins University
Two Linear Programs are Better than One
Oct 11, 2026Alexander E. Black, Christoph Hertrich, Stefan Kober +1Combinatorial Optimization Linear Programming
Department of Mathematics, Bowdoin College · Department Liberal Arts and Social Sciences, University of Technology Nuremberg · Department of Mathematics, London School of Economics and Political Science +1
Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
Oct 1, 2026Han Zhong, Yinyu YeRobust Markov Decision Processes Markov Decision Processes
Shanghai Jiao Tong University · Shanghai Jiao Tong University, SIMIS, and Stanford University
The Curvature of Regret in Contextual Linear Optimization
Oct 1, 2026Konstantinos Ziliaskopoulos, Alexander Vinel, Alice E. SmithDecision-Focused Learning Regret Minimization
Auburn University Auburn, AL, USA · University of Alabama Tuscaloosa, AL, USA
Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming
Oct 1, 2026Jinhwan Sul, Alex Oshin, Evangelos A. TheodorouPrimal-Dual Optimization Reinforcement Learning
Georgia Institute of Technology, USA
Predictive Dual Smoothing for Column Generation
Sep 28, 2026Senne Berden, Noah Schutte, Andrea Lodi +1Primal-Dual Optimization Linear Programming
KU Leuven · TU Delft · Cornell Tech
An Exact Junction-Tree Extended Formulation for Optimal Classification Trees
Sep 21, 2026Jiancheng TU, WenqiFanDecision Tree Learning Classification
Department of Computing, The Hong Kong Polytechnic University · Department of Management and Marketing, The Hong Kong Polytechnic University
Alignment of a Total Automation Economy
Jul 19, 2026David McAllesterAI Alignment Linear Programming
A $^{2}$ utoLPBench: An Auto-Generated, Agent-Friendly LP Benchmark via Inverse-KKT Construction
Jul 2, 2026Shuo Ren, Yaohui Han, Yifan Shi +6AI Agent Benchmarks Synthetic Benchmark Generation
The Chinese University of Hong Kong
Fixed-Parameter Tractability of Private Synthetic Data Generation
Jun 9, 2026Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +3Differentially Private Synthetic Data Generation Synthetic Data Generation
Google Deepmind · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Cat´olica de Chile · Google Research
Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming
Jun 7, 2026Siddharth Prasad, Dravyansh SharmaPrimal-Dual Optimization Constrained Optimization
Toyota Technological Institute at Chicago
Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A*
May 26, 2026Izack CohenAlgorithm Selection Process Mining
aFaculty of Engineering, Bar-Ilan University, Ramat Gan, Israel
Tokenisation via Convex Relaxations
May 21, 2026Jan Tempus, Philip Whittington, Craig W. Schmidt +2Token Efficiency Linear Programming
ETH Zurich · Kensho Technologies
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.
Asymmetric-Information Resource Allocation Games: An LP Approach to Purposeful Deception
Apr 27, 2026Longxu Pan, Yue Guan, Daigo Shishika +1Imperfect-Information Games Game Theory
Longxu Pan, Yue Guan, and Panagiotis Tsiotras are with the School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA, USA. · Daigo Shishika is with the College of Engineering and Computing, George Mason University, Fairfax, VA, USA.
Learning Decision-Sufficient Representations for Linear Optimization
Mar 19, 2026Yuhan Ye, Saurabh Amin, Asuman OzdaglarLinear Programming
MIT
Online Semi-infinite Linear Programming: Efficient Algorithms via Function Approximation
Mar 17, 2026Yiming Zong, Jiashuo JiangFunction Approximation Linear Programming
Department of Industrial Engineering & Decision Analytics, Hong Kong University of Science and Technology
A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
Mar 15, 2026Haoran Xu, Owen Shen, Peter Glynn +2Online Resource Allocation Linear Programming
Department of Management Science and Engineering, Stanford University · Operations Research Center, Massachusetts Institute of Technology
OptiRepair: Closed-Loop Diagnosis and Repair of Supply Chain Optimization Models with LLM Agents
Feb 23, 2026Ruicheng Ao, David Simchi-Levi, Xinshang WangSupply Chain Optimization Large Language Model-Guided Optimization
Massachusetts Institute of Technology. · Alibaba Group.
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
Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming
Jun 2, 2025Haruki Yokota, Hiroshi Higashi, Yuichi Tanaka +1Graph Structure Learning Graph Representation Learning
Infrequent Resolving Algorithm for Online Linear Programming
Aug 1, 2024Guokai Li, Zizhuo Wang, Jingwei ZhangSequential Decision Making Regret Minimization
School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, 518172, P.R. China
Online Linear Programming with Batching
Aug 1, 2024Haoran Xu, Peter W. Glynn, Yinyu YeSequential Decision Making Regret Minimization
Department of Management Science and Engineering, Stanford University
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
Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients
Mar 28, 2024Johannes Müller, Semih Çaycı, Guido MontúfarPolicy Gradient Optimization Convergence Analysis
Department of Mathematics, RWTH Aachen University, Aachen, 52062, Germany · Departments of Mathematics and Statistics & Data Science, University of California, Los Angeles, 90095, USA · Max Planck Institute for Mathematics in the Sciences, Leipzig, 04103, Germany
Equity Promotion in Online Resource Allocation
Dec 8, 2021Pan Xu, Yifan XuSequential Decision Making Fair Resource Allocation
Department of Computer Science, New Jersey Institute of Technology, Newark, USA · Key Lab of CNII, MOE, Southeast University, Nanjing, China

Oct 14, 2026J/K move · Enter open · S save

Learning Warm Starts for the Simplex Method from Measured Solver Cost

Felix Parker, Danielle A. Ripsman, Emmett Springer, Kimia Ghobadi

Center for Systems Science and Engineering, Johns Hopkins University

Linear Programming Learning to Optimize Algorithm Selection

Open paper AskPDF arXiv

Learned warm starts for the simplex method build starting bases using predictions of which variables will be basic at optimality. Prior work has shown that starting bases predicted by graph neural networks can sharply reduce iteration counts, but the time saved may fall well short of the iterations saved. On 25 classes of linear programs (LPs), we find that a strong supervised basis predictor removes two thirds of the dual simplex's iterations but only a third of its time. Two effects explain the gap: the iterations removed by a good start tend to be cheap, and closeness to an optimal basis does not rank starts by cost. We prove that two starts with equal overlap with an optimal basis and equal pivot counts can differ in linear-algebra work by a factor that grows with the square root of the number of rows. Empirically, across the starts of one LP, the pivot count explains 71% of the variance of log solve time, while the CPU instruction count explains 98.5%. We introduce CostStart, which uses supervised prediction for the basis and trains a small policy on measured instruction counts to choose, per LP, how many predicted columns to use, which algorithm and pricing rule to run, and whether to warm-start at all. On unseen LPs of the training classes, including LPs four times the training size, CostStart roughly halves the solve time relative to the solver's default start and is 1.4 to 2.2 times as fast as two published methods retrained on the same data.