mixed-integer programming

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

Solving Convex Quadratic Optimization with Indicators Over Structured Graphs

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

This paper studies convex quadratic minimization problems in which each continuous variable is coupled with a binary indicator variable. We focus on the structured setting where the Hessian matrix of the quadratic term is positive definite and exhibits sparsity. We develop an exact parametric dynamic programming algorithm whose computational complexity depends explicitly on the treewidth … Read more

Exact and Heuristic Methods for Gamma-Robust Min-Max Problems

Categories Bilevel Optimization, Combinatorial Optimization, Robust Optimization Tags , , , ,

Bilevel optimization is a powerful tool for modeling hierarchical decision-making processes, which arise in various real-world applications. Due to their nested structure, however, bilevel problems are intrinsically hard to solve—even if all variables are continuous and all parameters of the problem are exactly known. Further challenges arise if mixed-integer aspects and problems under uncertainty are … Read more

Asymptotically tight Lagrangian dual of smooth nonconvex problems via improved error bound of Shapley-Folkman Lemma

Categories Convex Optimization, Nonlinear Optimization Tags , ,

In convex geometry, the Shapley–Folkman Lemma asserts that the nonconvexity of a Minkowski sum of $n$-dimensional bounded nonconvex sets does not accumulate once the number of summands exceeds the dimension $n$, and thus the sum becomes approximately convex. Originally published by Starr in the context of quasi-equilibrium in nonconvex market models in economics, the lemma … Read more