mixed-integer programming

SDDmiP.jl: A Software Package with a Provably Convergent Benders Algorithm for Multi-Stage Stochastic Mixed-Integer Programming

Categories Optimization Software and Modeling Systems, Stochastic Programming Tags , , , , , ,

We present an open-source software package that implements a provably convergent Benders-type decomposition algorithm for multistage stochastic integer programs. In addition to standard cut families, such as Benders, strengthened Benders, and Lagrangian cuts, the algorithm incorporates rectified linear unit (ReLU) cuts, which provide convergence guarantees for general mixed-integer state variables. However, the dual problems used … Read more

Generalizing single-level relaxations for bilevel linear programs

Categories (Mixed) Integer Linear Programming, Bilevel Optimization Tags , ,

We consider a broad class of bilevel linear programs in which the follower’s decisions are all continuous, while the leader’s decisions may include integrality restrictions. Solving such problems to optimality is known to be NP-hard. A classical approach in bilevel optimization for constructing lower and upper bounds is based on a single-level relaxation, in which … Read more

Computing diverse solutions to optimization problems

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , ,

Classical optimization methods determine a single optimal or near-optimal solution for a decision problem. In many applications, however, the decision maker is interested in evaluating a pool of high-quality solutions, to encode fairness-oriented criteria or to obtain a portfolio of alternatives to use in case of unexpected scenarios. In this paper, we consider the problem … Read more

Route `Em and Count `Em: A Two-Stage Stochastic Programming Model for Anti-Submarine Operations

Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , ,

Tracking targets in undersea warfare requires successful detection by an active search asset. Maximizing detection likelihood requires strategic placement and routing of the search assets in the search region over the planning horizon. We develop a two-stage stochastic integer programming model that maximizes the expected total reward for target detections under uncertainty in target motion … Read more

Stochastic Queens Elimination

Categories (Mixed) Integer Linear Programming, Dynamic Programming Tags , , , ,

This research introduces the Stochastic Sequential Queens Elimination Problem, where on the \(n\)-queens board, each activated queen simultaneously attempts to eliminate all queens in her unblocked neighborhood, each independently succeeding with probability \(p\). The objective is to minimize the expected cumulative conflict count over the trajectory. This research proposes a Markov decision process for this … Read more

Spatial Optimization Models for Width-Constrained Wildlife Corridor Design

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Applications - Science and Engineering Tags , , ,

Human activities increasingly fragment natural habitats, placing many species at risk of population decline. This creates an urgent need to preserve biodiversity and maintain ecological connectivity through wildlife corridors. We present two spatial optimization models for corridor design that explicitly incorporate corridor width as a key ecological criterion. The first model minimizes total corridor cost … Read more

Nested Benders Decomposition for Large-Scale Multi-Follower Bilevel Optimization

Categories Bilevel Optimization, Parallel Algorithms, Transportation Tags , , , ,

We propose a scalable nested Benders decomposition (BD) framework for single-leader, multi-follower bilevel optimization problems. The proposed framework is applicable to bilevel optimization problems in which each follower solves a linear program and is particularly well suited for instances involving a large number of followers. By identifying the upper-level decisions as complicating variables, the method … Read more

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

Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Stochastic Programming Tags , , ,

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

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

Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , ,

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

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

Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms Tags , ,

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