Extended Formulations – Optimization Online

Small extended formulations for group-constrained flows and cographic integer hulls

Published: 2026/10/05

Avinash Bhardwaj

Graphs and Matroids, Integer Programming, Polyhedra bounded subdeterminants, cographic matroid, Extended Formulations, extension complexity, finite abelian group, network flow

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

The complete edge relaxation for binary polynomial optimization

Published: 2025/07/17

0-1 Programming, Global Optimization, Integer Programming binary polynomial optimization, Complete edge relaxation, Extended Formulations, Generalized triangle inequalities, hypergraph acyclicity, multilinear polytope

We consider the multilinear polytope defined as the convex hull of the feasible region of a linearized binary polynomial optimization problem. We define a relaxation in an extended space for this polytope, which we refer to as the complete edge relaxation. The complete edge relaxation is stronger than several well-known relaxations of the multilinear polytope, … Read more