Integer Programming – Page 4 – Optimization Online

Multi-Fidelity Benders Decomposition for Generation, Storage, and Transmission Expansion Planning

Published: 2026/04/29

Modern energy grid expansion planning, by necessity, includes timeseries data to accurately model storage and renewable assets. Representative time periods are commonly used as a way to decrease problem size and therefore mitigate the increased complexity from this inclusion. However, there are many choices around these representative periods: length; location in planning horizon; boundary conditions. … Read more

A polynomial-time solvable class of sparse box-constrained polynomial optimization problems

Published: 2026/04/28

Aida Khajavirad

(Mixed) Integer Nonlinear Programming binary polynomial optimization, box-constrained polynomial optimization, hypergraph, polynomial-time algorithm, sparsity, treewidth

We study the problem of minimizing a multivariate polynomial function over the unit hypercube. By representing the polynomial through a hypergraph and exploiting its sparsity structure, we establish a new sufficient condition under which the problem can be solved in time polynomial in the encoding length of the input. Our approach identifies a subset of … Read more

Probabilistic analysis of dual decomposition on two-stage stochastic integer programs

Published: 2026/04/25

Jingye Xu

Integer Programming, Stochastic Programming Decomposition methods, two-stage integer programming

Two-stage stochastic integer programs provide a powerful framework for modeling decision-making under uncertainty, but they are notoriously difficult to solve at scale due to their high dimensionality and intrinsic nonconvexity. Decomposition-based algorithms such as Benders methods and Branch-and-Price (related dual decomposition methods) have become standard computational approaches for such problems and demonstrate excellent empirical performance … Read more

Reverse stress testing for supply chains

Published: 2026/04/21, Updated: 2026/04/30

Applications - OR and Management Sciences, Integer Programming, Supply Chain Management optimization, risk identification, stress testing, supply chain resilience

This study introduces reverse stress testing for supply chains, designed to identify the minimal deviations from normal operations that would drive supply chains to a predefined performance failure. First, we present a framework for reverse stress testing with the purpose of assessing supply chain vulnerabilities. The framework involves six steps: selecting risk variables, defining baselines, … Read more

Enhancing the separation of rank-1 Chvátal-Gomory cuts from knapsack sets

Published: 2026/04/20

0-1 Programming, Branch and Cut Algorithms, Integer Programming chvatal-gomory cuts, cutting planes, generalized assignment problem, knapsack problem

We present an exact method for separating Chvátal-Gomory cuts from binary knapsack sets, consisting of two steps: i) enumerating a finite set of possible optimal multipliers for the knapsack constraint; ii) for each candidate, adjusting optimally the remaining multipliers. We prove that ii) can be formulated as a binary knapsack problem, leading to a pseudopolynomial-time … Read more

Pseudo-Compact Formulations and Branch-and-Cut Approaches for the Capacitated Vehicle Routing Problem with Stochastic Demands

Published: 2026/04/20

(Mixed) Integer Linear Programming, Branch and Cut Algorithms, Stochastic Programming branch-and-cut, mixed-integer programming, stochastic programming, vehicle routing problem

In this paper, we address the Capacitated Vehicle Routing Problem with Stochastic Demands (CVRPSD), in which routes are planned a priori and recourse actions are performed to ensure demand fulfillment. These recourse actions are defined through policies and may include replenishment trips or demand backlogging subject to penalties. We develop the first family of pseudo-compact … Read more

Pricing Discrete and Nonlinear Markets With Semidefinite Relaxations

Published: 2026/04/18

(Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Semi-definite Programming electricity market, pricing, semidefinite programming, strong duality, unit commitment

Nonconvexities in markets with discrete decisions and nonlinear constraints make efficient pricing challenging, often necessitating subsidies. A prime example is the unit commitment (UC) problem in electricity markets, where costly subsidies are commonly required. We propose a new pricing scheme for nonconvex markets with both discreteness and nonlinearity, by convexifying nonconvex structures through a semidefinite … Read more

A cut-based mixed integer programming formulation for the hop-constrained cheapest path problem

Published: 2026/04/15, Updated: 2026/04/16

Hamidreza Validi

Combinatorial Optimization, Integer Programming, Network Optimization graph theory, mixed-integer programming, the hop-constrained cheapest path problem

Given a simple graph G = (V, E) with edge cost c ∈ ℝ^|E|, a positive integer h, source s ∈ V and terminal t ∈ V, the hop-constrained cheapest path problem (HCCP) seeks to find an s–t path of length at most h hops with the cheapest cost. This paper proposes a cut-based mixed … Read more

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

Published: 2026/04/14

(Mixed) Integer Nonlinear Programming, Statistics Branch-and-Bound, hyperplane arrangements, Mixed-integer nonlinear optimization, robust statistics

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 … Read more

Machine-learning-enhanced strategies to generate subtour elimination constraints for the symmetric traveling salesman problem

Published: 2026/04/13

Combinatorial Optimization, Integer Programming branch-and-cut, exact algorithms, integer programming, machine learning, Travelling salesman

We present a machine learning (ML) component designed to enhance the well-known branch-and-cut (B&C) framework for the symmetric traveling salesman problem (TSP) in which only the subtour elimination constraints (SECs) violated by previously found integer solutions are considered. The objective of the ML component is to identify which SECs, from a pool of candidates, will … Read more