Interdiction for the direct current optimal power flow problem is commonly modeled in two stages, where an attacker disables components in the first stage and an operator makes remedial adjustments in the second stage. The resulting bilevel mathematical program is often solved via transformation into a single-level mixed-integer program using duality. A drawback of this … 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
This paper investigates a presolving method for handling symmetries in mixed-integer programs, based on inequalities computed from so-called Schreier-Sims tables. We show that an iterative application of this method together with merging variables produces an instance for which the symmetry group is trivial. We then prove that the problem structure can be preserved for certain … Read more
Let the elements of a matroid be labeled in an abelian group, and let \(F\) be a finite set of forbidden basis-label sums. We prove that, for every representable matroid, every basis is within \(|F|\) exchanges of an \(F\)-avoiding basis whenever one exists. This resolves the unweighted proximity conjecture for representable matroids over arbitrary fields, … Read more
Abstract: A three-way transportation polytope consists of nonnegative three-way arrays with prescribed sums along every coordinate line. We show that its geometry and the difficulty of finding its integer points are both controlled by one local quantity: the number of cells on a line that can be positive. The change happens between two and three. … Read more
Linear inequalities can generate large constraint systems in semidefinite relaxations of binary quadratic programs, making the quadratic subproblems of splitting methods expensive to solve. We develop a box-cone representation of bound-factor reformulation-linearization technique (RLT) constraints in semidefinite relaxations of binary quadratic programs. These constraints arise by multiplying each original linear inequality by every binary variable … Read more
Since its introduction in 2013, the dotted-board model has been widely used by the cutting and packing research community to tackle irregular packing problems. However, despite its popularity, little research has aimed at improving its performance when solved via off-the-shelf integer programming solvers, beyond the known strategy of merging pairwise incompatibility constraints into clique constraints … Read more
A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. For such polyhedra, integer feasibility is in NP ∩ coNP by a result of Boyd and Pulleyblank from the early 1980s, so it is unlikely to be NP-hard. Whether it is polynomial has remained open … Read more
An instance of the quadratic minimum spanning tree problem (QMSTP) is called linearizable if it can be rewritten as an instance of the linear minimum spanning tree problem in such a way that the objective function value is preserved at all feasible solutions. Previous work has shown that a sufficient condition for linearizability is that … Read more
We construct small extended formulations for nonnegative integer flows whose arc labels have a prescribed sum in a finite abelian group. For circulations, the formulation is a single integral network that combines cycles even when they lie in different components. This yields an O(Δn²) bound for strictly Δ-modular cographic integer hulls of translated cones, improving … Read more