Mixed Integer Programming Workshop 2026

Abstract: Many stochastic dynamic systems can be modeled as collections of interacting components linked by shared combinatorial constraints. Canonical examples include inventory allocation over time, tour scheduling under capacity limits, and healthcare resource management across patient classes. A widely used approximation paradigm applies Lagrangian or fluid relaxations that decompose the system into marginal flow models for individual components, enforcing coupling constraints only through post-processing steps such as sampling, projection, or rounding.

We show that this paradigm implicitly follows an allocate-then-correct structure: it first allocates probability mass over actions using a linear program defined on a marginal flow relaxation, and only afterward projects the resulting solution onto the feasible action space. From a polyhedral standpoint, the marginal relaxation can strictly contain the convex hull of feasible joint actions, introducing fractional action distributions that are not implementable by any feasible policy. This structural gap induces an aggregate infeasibility bias, forcing corrective adjustments that may substantially degrade policy performance and increase the need for repeated reoptimization.

To address this limitation, we reverse the underlying logic. Instead of relaxing the feasible action set, we construct marginalized linear programs over the convex hull of feasible action subsets, yielding a strictly strengthened formulation that enforces coupling constraints by construction. The resulting models admit an interpretation as extended formulations of the underlying action polytope and eliminate the need for ex post correction. Furthermore, any polynomial-time approximation algorithm for generating feasible action sets induces a tractable corresponding approximate extended formulation of the action polytope, with the approximation ratio translating directly into bounds on the model performance.

Building on these models, we introduce a new policy class that enforces feasibility by construction and eliminates the need for corrective rounding. Computational experiments on dynamic assortment and maintenance problems illustrate regimes in which convexified formulations reduce infeasibility corrections, improve stability, and outperform classical fluid relaxations. Beyond these applications, the results suggest a broader methodological principle: in coupled dynamic systems, convexification of feasible action sets can provide a structurally stronger alternative to marginal flow relaxations.

Abstract: We study the alternating gradient descent-ascent (AltGDA) algorithm in two-player zero-sum games. Alternating methods, where players take turns to update their strategies, have long been recognized as simple and practical approaches for learning in games, exhibiting much better numerical performance than their simultaneous counterparts. However, our theoretical understanding of alternating algorithms remains limited, and results are mostly restricted to the unconstrained setting. We show that for two-player zero-sum games that admit an interior Nash equilibrium, AltGDA converges at an $\mathcal{O}(1/T)$ ergodic convergence rate when employing a small constant stepsize. This is the first result showing that alternation improves over the simultaneous counterpart of GDA in the constrained setting. For games without an interior equilibrium, we show an $\mathcal{O}(1/T)$ local convergence rate with a constant stepsize that is independent of any game-specific constants. In a more general setting, we develop a performance estimation programming (PEP) framework to jointly optimize the AltGDA stepsize along with its worst-case convergence rate. The PEP results indicate that AltGDA may achieve an $\mathcal{O}(1/T)$ convergence rate for a finite horizon T, whereas its simultaneous counterpart appears limited to an $\mathcal{O}(1/\sqrt{T})$ rate.

Joint work with Tianlong Nan, Garud Iyengar, and Christian Kroer.

Abstract: An extremely fruitful line of algorithms research over the past decade has been the application of interior point methods alongside data structure design to classical problems in combinatorial optimization. In this talk, we consider linear programs of the form $\min \langle c,x \rangle$ subjected to $Ax = b$, $x \geq 0$, where the constraint matrix $A$ has suitable structural properties. We present a general framework for solving these structured linear programs that ties together interior point methods and tools across theoretical computer science including graph decomposition, sampling, dynamic algorithms, and numerical linear algebra. Our framework in turn yields the fastest-known algorithms for min-cost flow and k-commodity flow on planar graphs, and for min-cost flow and general linear programs on graphs with bounded treewidth.

Based on joint work with Yu Gao, Gramoz Goranci, Yin Tat Lee, Lawrence Li, Richard Peng, Sushant Sachdeva, and Guanghao Ye.

Abstract: Mixed‑Integer Linear Programming (MILP) has been the dominant optimization framework in Operations Research for several decades. While it has proven extremely powerful, it is also well known that MILP formulations can become unwieldy when confronted with large‑scale, highly combinatorial, non‑convex, or structurally rich problems, particularly in application domains such as routing, scheduling, and packing.

Hexaly is an industrial optimization solver built around a hybrid, post‑MILP approach. Rather than relying primarily on linearization techniques and classical branch‑and‑bound‑centered workflows, it combines heuristic and exact methods and draws inspiration from multiple paradigms, including Mixed‑Integer Programming, Constraint Programming, Nonlinear Programming, and Black‑Box Optimization. A central design objective is modeling expressiveness and openness: enabling users to formulate problems closer to their natural combinatorial structure, while allowing diverse algorithmic components to interact in a complementary manner.

In this talk, I will present the guiding principles behind this approach, with a particular focus on discrete optimization problems where Hexaly currently demonstrates its strongest performance, such as large‑scale routing, scheduling, and packing. I will discuss how hybridization manifests not only at the algorithmic level, but also—crucially—within the modeling layer. Finally, I will provide a transparent overview of the solver’s current algorithmic status, supported by selected performance benchmarks.

Abstract: Dual solutions in MILP are typically obtained as a by-product of solving LP relaxations at the nodes of the branch-and-bound tree. These dual solutions are globally valid and can be leveraged across the tree and reused in other components such as bound tightening. However, storing and processing a large number of dual solutions can be computationally expensive.

In this work, we propose practical methods to generate dual solutions for local use within the search tree. In particular, we either modify existing dual solutions or combine multiple dual solutions to produce new ones. Furthermore, we investigate primal–dual relationships to better exploit their interaction to improve the effectiveness of bound tightening.

Abstract: State-of-the-art neural network (NN) verifiers demonstrate that applying the branch-and-bound (BaB) procedure with fast bounding techniques plays a key role in tackling many challenging verification properties. In this work, we introduce the linear constraint-driven clipping framework, a class of scalable and efficient methods designed to enhance the efficacy of NN verifiers. Under this framework, we develop two novel algorithms that efficiently utilize linear constraints to 1) reduce portions of the input space that are either verified or irrelevant to a subproblem in the context of branch-and-bound, and 2) directly improve intermediate bounds throughout the network. The process leverages novel linear constraints that often arise from bound propagation methods and is general enough to incorporate constraints from other sources. It efficiently handles linear constraints using a specialized GPU procedure that can scale to large neural networks without the use of expensive external solvers. Our verification procedure, Clip-and-Verify, consistently tightens bounds across multiple benchmarks and can significantly reduce the number of subproblems handled during BaB. We show that our clipping algorithms can be integrated with BaB-based verifiers such as $\alpha,\beta$-CROWN, utilizing either the split constraints in activation-space BaB or the output constraints that denote the unverified input space. We demonstrate the effectiveness of our procedure on a broad range of benchmarks where, in some instances, we witness a 96% reduction in the number of subproblems during branch-and-bound, and also achieve state-of-the-art verified accuracy across multiple benchmarks.

Abstract: Hamiltonian simulation is one of the first proposed uses for quantum computers. In order to perform Hamiltonian simulation, one has to encode the Hamiltonian, which describes the dynamics of a quantum system, into a quantum computer. This can be challenging since current quantum computers are limited in size and connectivity, and are prone to error. In this work, we introduce a graph matching algorithm for approximating continuous-time quantum walk Hamiltonians. The algorithm requires only polynomial classical overhead and results in smaller circuits (and therefore higher fidelity output) than Pauli decomposition, a standard algorithm used to decompose Hamiltonians, for sparse graphs.

Abstract: PDLP is a first-order method for linear programming based on a standard first-order method, PDHG, combined with several novel heuristics. This talk will discuss the ideas behind the primal weight, feasibility polishing and restart heuristics for PDLP, and showcase our latest results on a newly constructed suite of large-scale linear programming problems.

Abstract: Unit commitment is a core application of mixed-integer optimization, but incorporating exact AC network constraints turns it into a much harder mixed-integer nonlinear problem. In this talk, I will present a decomposition-based approach for UC-ACOPF that separates the integer unit commitment structure from the nonlinear ACOPF subproblems. The reformulation yields generator-wise UC subproblems that are solved exactly by dynamic programming and decomposes the AC side into many small nonlinear subproblems that can be processed efficiently on GPUs. I will discuss why this viewpoint is natural from a MIP perspective, how it preserves the combinatorial core of unit commitment while handling nonconvex grid physics, and what the numerical results show relative to standard solver-based baselines on IEEE test cases. I will close with a brief outlook on a related direction: learning shared representations across ACOPF, SCUC, and UC-ACOPF to support systematic generalization across related grid optimization problems.

Abstract: We design a machine learning (ML)-guided enhancement of the Undercover primal heuristic for mixed-integer nonlinear programs (MINLPs). Undercover identifies a subset of variables to fix and assigns them values, thereby restricting the MINLP to a mixed-integer linear program (MILP) that can be solved using off-the-shelf solvers to potentially obtain a feasible solution. While Undercover performs well on mixed-integer quadratically constrained quadratic programs (MIQCQPs), its effectiveness on general MINLPs is limited by the difficulty of choosing good fixing values. To address this challenge, we propose a graph convolutional network (GCN) that predicts high-quality fixing values for selected variables. The model is pretrained using best-known feasible solutions and further optimized through a task-based loss function. We integrate our ML-guided Undercover heuristic within the global solver SCIP and evaluate it on benchmark instances from QPLIB and MINLPLIB. Computational results demonstrate that the proposed approach improves the performance of the default Undercover implementation in SCIP.

Abstract: Many design, planning and decision problems arising in engineering, sciences, finance, and statistics can be modeled as mixed-integer nonlinear optimization problems. A challenging class of mixed-integer problems are topology design problem, arising in additive manufacturing or the design of cloaking devices. In topology optimization, the physical response of the design is modeled as partial-differential equations (PDEs) and the design is modeled with binary variables defined on each element of the discretization of the PDE. This approach results in mixed integer PDE-constrained optimization (MIPDECO) problem that combine the computational challenges of PDEs with the combinatorial challenges of a massive number of discrete variables. We a number of efficient and scalable optimization algorithms based on rounding and randomized search techniques and discuss their optimality properties. We illustrate these solution techniques with examples from topology optimization.

Abstract: Convex maximization arises in many applications but is generally NP-hard, even for low-rank objectives. This paper introduces a set of broadly applicable conditions that certify when such problems are polynomially solvable. Our main condition is a new property of the feasible set, which we term comonotonicity. We show that this property holds for two important families: matroids and permutation-invariant sets. Under comonotonicity and mild additional assumptions, we develop a geometric framework that generates polynomially many candidate solutions, one of which is optimal. This yields a polynomial-time algorithm. We further derive substantially sharper complexity bounds when the feasible set is permutation-invariant. Our framework recovers existing tractable instances and often improves their complexity. It also expands the frontier of tractability by providing the first polynomial-time guarantees for new applications.

This is joint work with Shaoning Han and Liangju Li from National University of Singapore.

Abstract: We present a GPU-accelerated method for compiling multi-valued decision diagrams (MDDs) for dynamic programming models. MDD construction expands states in layers defined by their distance from the root, a structure that enables independent parallel expansion of all states in a layer. We exploit this by partitioning each layer into limited-size fragments and executing the full expansion of each fragment on the GPU, including successor generation, dominance filtering, duplicate elimination, and pruning of suboptimal states.

By systematically traversing fragments in a depth-first manner, we obtain a parallel Complete Anytime Decision Diagram Search that preserves exactness and anytime behavior. Applied to the Traveling Salesman Problem with Time Windows, our implementation yields speedups of up to two orders of magnitude, and outperforms other state-based methods as well as a state-of-the-art dedicated optimization method for this application.

Abstract: Quadratically constrained quadratic programs (QCQPs) form a broad class of nonconvex optimization problems arising in applications such as energy infrastructure networks and pooling, yet they can be slow to solve to global optimality in practice. Motivated by the effectiveness, and sensitivity, of partitioning within MIP-based relaxations, we introduce strong partitioning policy: choosing variable-domain partitions to strengthen relaxations while preserving global optimality guarantees. Because computing this optimal (oracle) partitioning policy is expensive, we learn an efficient approximation for parameterized families of QCQPs using machine learning. Further, we propose a novel end-to-end training objective that directly rewards partitioning schemes with desirable relaxation/algorithmic properties, avoiding reliance on a fixed hand-designed policy as labels, and we develop a graph-based approach that enables a single model to generalize across problem sizes. Numerical results show that the learned policies generalize to unseen instances (including new sizes) and significantly reduce the runtime of partitioning-based globally convergent iterative algorithms.

Abstract: We introduce and study a directed analogue of the weighted Tree Augmentation Problem (WTAP). In the weighted Directed Tree Augmentation Problem (WDTAP), we are given an oriented tree $T = (V, A)$ and a set of directed links $L \subseteq V \times V$ with positive costs. The goal is to select a minimum cost set of links which enters each fundamental dicut of $T$ (cuts with one leaving and no entering tree arc). WDTAP captures the problem of covering a cross-free set family with directed links. It can also be used to solve weighted multi 2-TAP, in which we must cover the edges of an undirected tree at least twice. WDTAP can be approximated to within a factor of 2 using standard techniques. We provide an improved $(1.75 + \varepsilon)$-approximation algorithm for WDTAP in the case where the links have bounded costs, a setting that has received significant attention for WTAP. To obtain this result, we discover a class of instances, called “willows”, for which the natural set covering LP is an integral formulation. We further introduce the notion of “visibly k-wide” instances which can be solved exactly using dynamic programming. Finally, we show how to leverage these tractable cases to obtain an improved approximation ratio via an elaborate structural analysis of the tree.

This result is joint work with Olha Silina and Michael Zlatin and appeared in the proceedings of SODA 2026.

Abstract: Hallmark features of optimization models in heavy industry are their apparent lack of special structure (often also involving nonlinearities) and the large size of their corresponding instances. Therefore, careful formulation and solution techniques are imperative to obtain implementable solutions in an operationally feasible amount of time. Drawing on examples from mine planning, steel manufacturing, concentrated solar power production, and power systems, we show how appropriate model scope, identification of initial feasible solutions, tight formulations, correct algorithmic choice, and, in some cases, tailored decomposition schemes, effect implementable actions. We conclude with a contrast to light industry.

Abstract: Motivated by our collaboration with a residency program at an academic health system, we propose new integer programming (IP) approaches for the resident-to-rotation assignment problem (RRAP). Given sets of residents, resident classes, and departments, as well as a block structure for each class, staffing needs, rotation requirements for each class, program rules, and resident vacation requests, the RRAP involves finding a feasible year-long rotation schedule that specifies resident assignments to rotations and vacation times. We first present an IP formulation for the RRAP, which mimics the manual method for generating rotation schedules in practice and can be easily implemented and efficiently solved using off-the-shelf solvers. However, it can lead to disparities in satisfying vacation requests among residents. To mitigate such disparities, we derive a fairness-promoting counterpart that finds an optimal rotation schedule, maximizing the number of satisfied vacation requests while minimizing a measure of disparity in satisfying these requests. Then, we propose a computationally efficient Pareto Search Algorithm capable of finding the complete set of Pareto optimal solutions to the fairness-promoting IP within a time that is suitable for practical implementation. Additionally, we present a user-friendly tool that implements the proposed models to automate the generation of the rotation schedule. Finally, we construct diverse RRAP instances based on data from our collaborator and conduct extensive experiments to illustrate the potential practical benefits of our proposed approaches. Our results demonstrate the computational efficiency and implementability of our approaches and underscore their potential to enhance fairness in resident rotation scheduling.

Abstract: The study of first-order methods for convex optimization has historically been framed in terms of a priori worst-case convergence rates/guarantees. Within this paradigm, recent advances in the Performance Estimation Program (PEP) framework have enabled the discovery of provably minimax-optimal algorithms. While natural and powerful, an exclusive focus on a priori worst-case guarantees limits our ability to reason about dynamic, beyond worst-case behavior. To address this gap, we adopt a game-theoretic view of algorithm design inspired by subgame perfection. This lens allows us to formalize and analyze dynamically optimal, subgame perfect algorithms and their relaxations, thereby capturing stronger notions of dynamic optimality.

This talk serves as an introduction to the PEP framework and the recent advances in subgame perfect algorithm design.

Based on joint work with Benjamin Grimmer and Kevin Shu

Abstract: Discrete optimization has become an emerging area of impact in modern machine learning, including mixed-integer programming (MIP), graph optimization, and routing problems. This talk presents two forays into machine learning for MIP. First, we identify that MIP solvers can be drastically accelerated by appropriately selecting cutting plane separators to activate. As the combinatorial separator selection space imposes challenges for machine learning, we learn to separate by proposing a novel data-driven strategy to restrict the selection space and a learning-guided algorithm on the restricted space. Our method predicts instance-aware separator configurations which can dynamically adapt during the solve, effectively accelerating the open source MILP solver SCIP by improving the relative solve time up to 72% and 37% on synthetic and real-world MIP benchmarks. Second, we address a severe shortage of training data for MIP foundation models by introducing MILP-Evolve, a novel LLM-based evolutionary framework that is capable of generating a large set of diverse MIP classes with an unlimited amount of instances. We study our methodology on three key learning tasks that capture diverse aspects of MIP: (1) integrality gap prediction, (2) learning to branch, and (3) a new task of aligning MIP instances with natural language descriptions. Our empirical results show that models trained on the data generated by MILP-Evolve achieve significant improvements on unseen problems, including MIPLIB benchmarks.

Bio: Cathy Wu is the Class of 1954 Career Development Professor at MIT, holding appointments in LIDS, CEE, and IDSS. She holds a Ph.D. in EECS from UC Berkeley, and B.S. and M.Eng. in EECS from MIT, and completed a Postdoc at Microsoft Research. Her research group studies machine learning for optimization, with a focus on transportation. She is broadly interested in enabling faster, evidence-driven decisions for sociotechnical systems. Cathy is the recipient of the NSF CAREER (2023), the Ole Madsen Mentoring Award (2025), the IEEE ITS Best Dissertation Award (2019), and the CUTC Milton Pikarsky Memorial Award (2018). She serves on the Board of Governors for the IEEE ITSS, is an Associate Editor or Area Chair for ICML, NeurIPS, ICRA, Transportation Research Part C, and Operations Research, and served as Program Co-chair for RLC 2025. She is also the inaugural Chair and Co-founder of the REproducible Research In Transportation Engineering (RERITE) Working Group.