## A Stochastic Benders Decomposition Scheme for Large-Scale Data-Driven Network Design

Network design problems involve constructing edges in a transportation or supply chain network to minimize construction and daily operational costs. We study a data-driven version where operational costs are uncertain and estimated on historical data. This problem is computationally challenging, and instances with as few as 50 nodes cannot be solved to optimality by current … Read more

## Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator

 We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator $$\text{LS}_+$$, with a particular focus on a search for relatively small graphs with high $$\text{LS}_+$$-rank (the least number of iterations of the $$\text{LS}_+$$ operator on the fractional stable set polytope to compute … Read more

## On Supervalid Inequalities for Binary Interdiction Games

Supervalid inequalities are a specific type of constraints often used within the branch-and-cut framework to strengthen the linear relaxation of mixed-integer programs. These inequalities share the particular characteristic of potentially removing feasible integer solutions as long as they are already dominated by an incumbent solution. This paper focuses on supervalid inequalities for solving binary interdiction … Read more

## Submodular maximization and its generalization through an intersection cut lens

 We study a mixed-integer set $$\mathcal{S}:=\{(x,t) \in \{0,1\}^n \times \mathbb{R}: f(x) \ge t\}$$ arising in the submodular maximization problem, where $$f$$ is a submodular function defined over $$\{0,1\}^n$$. We use intersection cuts to tighten a polyhedral outer approximation of $$\mathcal{S}$$. We construct a continuous extension $$\mathsf{F}$$ of $$f$$, which is convex and defined over … Read more

## Monoidal Strengthening of Simple V-Polyhedral Disjunctive Cuts

Disjunctive cutting planes can tighten a relaxation of a mixed-integer linear program. Traditionally, such cuts are obtained by solving a higher-dimensional linear program, whose additional variables cause the procedure to be computationally prohibitive. Adopting a V-polyhedral perspective is a practical alternative that enables the separation of disjunctive cuts via a linear program with only as … Read more

## Recovering Dantzig-Wolfe Bounds by Cutting Planes

Dantzig-Wolfe (DW) decomposition is a well-known technique in mixed-integer programming for decomposing and convexifying constraints to obtain potentially strong dual bounds. We investigate Fenchel cuts that can be derived using the DW decomposition algorithm and show that these cuts can provide the same dual bounds as DW decomposition. We show that these cuts, in essence, … Read more

## On the strength of recursive McCormick relaxations for binary polynomial optimization

Recursive McCormick relaxations have been among the most popular convexification techniques for binary polynomial optimization problems. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal recursive sequence amounts to solving a difficult combinatorial optimization problem. In this paper, we prove that any … Read more

## Superadditive duality and convex hulls for mixed-integer conic optimization

We present an infinite family of linear valid inequalities for a mixed-integer conic program, and prove that these inequalities describe the convex hull of the feasible set when this set is bounded and described by integral data. The main element of our proof is to establish a new strong superadditive dual for mixed-integer conic programming … Read more

## Copositive programming for mixed-binary quadratic optimization via Ising solvers

Recent years have seen significant advances in quantum/quantum-inspired technologies capable of approximately searching for the ground state of Ising spin Hamiltonians. The promise of leveraging such technologies to accelerate the solution of difficult optimization problems has spurred an increased interest in exploring methods to integrate Ising problems as part of their solution process, with existing … Read more

## Relaxations and Cutting Planes for Linear Programs with Complementarity Constraints

We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based on identifying vertex covers of the conflict graph of the instance and generalizes the extended reformulation-linearization technique of Nguyen, Richard, and Tawarmalani to instances with general complementarity conditions between variables. We demonstrate … Read more