Binary bilevel programs are challenging to solve due to the lack of compact single-level reformulations. Recent extended network flow-based reformulations have emerged as a promising approach, providing strong dual bounds. However, their increasing size can make them computationally prohibitive. We develop a cutting-plane framework that exploits these networks without requiring an extended-space formulation. We introduce … Read more
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
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
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
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
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
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
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
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
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