We study the k-delete recoverable robust 0–1 problem in which a decision-maker solves a combinatorial optimization problem subject to objective uncertainty. The model follows a two-stage robust setup. The decision-maker first commits to an initial plan and may then revoke up to k components of this decision after the uncertainty is revealed. The underlying uncertainty … Read more
Minimum distance constraints (minDCs) appear in many geometric optimization problems. They pose major challenges for mixed-integer nonlinear programming (MINLP) due to their reverse-convexity. We develop new algorithms for tightening variable bounds in general MINLPs with minDCs. Because many such problems exhibit substantial symmetry, we further introduce a practical approach for handling rotation symmetries via separation … Read more
Many large-scale optimization problems decompose into a master problem and scenario subproblems, a structure that can be exploited by Benders decomposition. In Benders decomposition, each iteration may generate many cuts from scenario subproblems, and adding all of them as constraints then causes the master problem to grow rapidly. These are constraints that may need to … Read more
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
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
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
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
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
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
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