(Mixed) Integer Linear Programming

A New Exact Algorithm for Continuous-Time Service Network Design with Splittable Deliveries

Published: 2026/10/29

(Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Network Optimization continuous time, dynamic discretization discovery, exact algorithm, service network design, Splittable delivery

The Continuous-Time Service Network Design Problem (CTSNDP) arises in consolidation-based transportation systems, where shipments share paths in space and time to reduce cost. The CTSNDP determines minimum-cost transportation plans over a continuous-time horizon. To provide more consolidation opportunities and achieve further cost reductions, CTSNDP with Splittable Deliveries (SCTSNDP) allows each commodity to be divided into … Read more

Asymptotic convexity in multistage stochastic mixed-integer programs

Published: 2026/10/26

(Mixed) Integer Linear Programming, Stochastic Programming Asymptotic convexity, mixed-integer programming, Multistage recourse models, stochastic programming

We consider multistage stochastic mixed-integer programs M-SMIPs, and show that these problems are asymptotically convex. That is, we show that the expected cost-to-go functions in the problem converge to convex functions as the variability of the random parameters in the model increases. To derive this result, we first propose a novel adapted Gomory relaxation for … Read more

Constraint Learning by Optimizing over Trained Neural Networks: A Pragmatic Tutorial

Published: 2026/10/24, Updated: 2026/10/26

(Mixed) Integer Linear Programming, Nonlinear Optimization

Constraint learning is an emerging paradigm of modeling optimization problems with the help of machine learning. In this paradigm, trained machine learning models are embedded into the optimization model. For example, we can learn constraints empirically from available data, or we can avoid using a nonlinear objective function by learning a simpler approximation for it. … Read more

Mixed-Integer Linear Reformulations of Pessimistic Bilinear Bilevel Infima

Published: 2026/10/23, Updated: 2026/10/25

(Mixed) Integer Linear Programming, Bilevel Optimization, Nonlinear Optimization bilinear optimization, Decision-focused learning, pessimistic bilevel optimization

We study pessimistic bilevel optimization with bilinear objectives and linear constraints. Assuming a compact polyhedral leader domain, nonempty follower solution sets, and a finite pessimistic infimum, we derive mixed-integer linear optimization formulations that attain this infimum, even when the original problem has no optimal solution. This setting has applications such as pricing, security, and decision-focused … Read more

The Strength of Root Cuts in an Extended Abstract Branch-and-Cut Model

Published: 2026/10/23

(Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming branch and cut algorithms, local cuts, mixed integer optimization, root cuts

The branch-and-cut paradigm has led to effective solvers for a wide range of mathematical optimization problems. Despite significant theoretical work on pure branching and pure cutting, less is known about their interaction. We study an extended abstract branch-and-cut model to investigate tradeoffs between branching and cutting, including the time to generate cuts. We prove that, … Read more

A Formulation for Power Flow Interdiction with Bounded Big-M Values

Published: 2026/10/19

(Mixed) Integer Linear Programming, Bilevel Optimization, Network Optimization big-m, bilevel optimization, interdiction, optimal power flow

Interdiction for the direct current optimal power flow problem is commonly modeled in two stages, where an attacker disables components in the first stage and an operator makes remedial adjustments in the second stage. The resulting bilevel mathematical program is often solved via transformation into a single-level mixed-integer program using duality. A drawback of this … Read more

Distributional Lifting for Discrete Optimization

Published: 2026/10/18, Updated: 2026/10/20

(Mixed) Integer Linear Programming, Convex Optimization, Nonlinear Optimization continuous reformulation, decision-dependent stochastic optimization, mixed-integer programming

We introduce a framework that transforms discrete optimization into continuous optimization over parameterized probability distributions. The framework reveals a common distributional structure behind several methods that have largely developed independently, including continuous reformulations for multilinear binary optimization, Markov decision processes and reinforcement learning, the cross-entropy method, mean-field variational optimization, and the quantum approximate optimization algorithm. … Read more

K-Adaptability in Stochastic Integer Optimization with Recourse

Published: 2026/10/02

(Mixed) Integer Linear Programming, Stochastic Programming k-adaptability, parametric optimization, Stochastic integer optimization

Many optimization problems solved repeatedly in practice, such as in power systems or logistics, share a fixed structure but with different parameter values. Re-optimizing each instance from scratch can be computationally prohibitive, while adopting a single solution for all realizations is overly conservative. The K-adaptability paradigm offers a flexible compromise by precomputing a small set … Read more

Signed Budget Uncertainty for Robust Mixed-Integer Optimization

Published: 2026/09/30

(Mixed) Integer Linear Programming, Robust Optimization Laminar Families, mixed integer optimization, robust optimization, Signed Budget Uncertainty

Classical budget uncertainty is widely used in robust optimization. It bounds the aggregate absolute deviation of uncertain parameters from nominal values and yields tractable robust counterparts. In many applications, however, information concerns aggregate signed deviations. We therefore study signed budget uncertainty, in which bounds are imposed on signed aggregates rather than absolute deviations. For robust … Read more

A sufficient convergence condition for generalized Benders decomposition with general dual functions

Published: 2026/09/22

Bingqian Liu

(Mixed) Integer Linear Programming, Convex and Nonsmooth Optimization, Convex Optimization, Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming finite convergence, general dual function, generalized benders decomposition, uniform local strongness

We revisit the framework of generalized Benders decomposition over a compact but non-finite master domain. We show by counterexample that strong general dual functions alone may fail to guarantee convergence. We then define a condition of uniform local strongness and prove that strong general dual functions satisfying this condition guarantee finite \(\epsilon\)-termination. Finally, we show … Read more