We study energy-efficient operation of underground train networks, where energy from regenerative braking is usable only if another train in the same electrically isolated subnetwork accelerates simultaneously. Timetabling models for this setting typically fix one velocity profile per leg and running time, which limits the matching of braking and accelerating phases. We drop this assumption … Read more
Imagine that you are in front of a cockpit with several on–off buttons. If you were to thoroughly test it, you would need to try a prohibitive number of configurations. But since most bugs in practice can be isolated to interactions among few components, having tests that cover every possible pairwise configuration is a good … Read more
Primal heuristics for finding high-quality feasible solutions are an important component in mixed-integer optimization (MIO) solvers. Recent advances in GPU-accelerated optimization algorithms show the potential of GPU acceleration for continuous optimization. In this paper, we introduce the Parallel Node Generation and Exploration Algorithm (PaNGEA), a GPU-friendly MIO primal heuristic. PaNGEA explores restricted subproblems by combining … 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
We study the convex hull obtained after deleting prescribed vertices from the binary cube. The analysis separates three regimes according to the number of deleted vertices. When this number is fixed, both the original-space facet count and the linear extension complexity remain linear in the ambient dimension, up to constants depending only on the number … 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 study adjustable robust network design for potential-based flows with controllable elements under load uncertainty. The resulting problem combines discrete here-and-now expansion decisions with wait-and-see operational decisions governed by nonconvex flow constraints. Moreover, controllable elements introduce adjustable integer decisions, which are algorithmically challenging. We equivalently characterize robust feasibility and robust optimality of a fixed network … Read more
We consider mixed-integer linear-quadratic generalized Nash equilibrium problems, i.e., games in which each player solves a mixed-integer program subject to linear constraints in her own and rivals’ strategies as well as an objective which is quadratic in her own strategies and bilinear in her own and rivals’ strategies. For this class of games, we study … Read more
This paper proposes BPCOL+, an exact branch-and-price algorithm for the Graph Coloring Problem. The algorithm is both novel and highly effective, integrating enhanced pricing strategies within Zero-Suppressed Binary Decision Diagrams (ZDDs) to efficiently solve the pricing problem associated with the maximal-stable-set-based set-covering formulation. After computing upper and lower bounds at the root node using heuristic … Read more