## Invited Session Wed.1.H 3004

#### Wednesday, 10:30 - 12:00 h, Room: H 3004

**Cluster 2: Combinatorial optimization** [...]

### Extended formulations in discrete optimization II

**Chair: Gautier Stauffer and Volker Kaibel**

**Wednesday, 10:30 - 10:55 h, Room: H 3004, Talk 1**

**Mathieu Van Vyve**

Projecting an extended formulation

**Coauthor: Laurence A. Wolsey**

**Abstract:**

What can be done when faced with a hard MIP for which a strong extended formulation is known, but is too large to be used in a branch-and-bound framework? One possible approach is as follows.

Given an extended formulation *Q={(x,w) ∈ ***R**^{n} × **R**^{q}|Bx + Dw ≥ d} and an objective *min c*^{T}x, we would like to efficiently derive a strong relaxation *P={x ∈ ***R**^{n} | Ax ≥ b} in the original variable space.

To be more specific, we would like the inequalities *Ax ≥ b* to be at the same time:

(i) such that the optimal solution sets of optimizing over *P* or *Q* are the same,

(ii) small: the number of inequalities is not too large, or even minimal, so that *Ax ≥ B* can efficiently replace *Bx + Dw ≥ d* in branch-and-bound,

(iii) efficiently computable,

(iv) individually strong: each of the inequality is ideally a facet of *proj*_{x}(Q),

(v) collectively strong: *P* is a strong relaxation of *proj*_{x}(Q).

We formalize these different requirements, discuss their compatibility, describe a practical scheme for solving MIPs for which a strong-but-too-large extended formulation is known, and present some computational experiments.

**Wednesday, 11:00 - 11:25 h, Room: H 3004, Talk 2**

**Kanstantsin Pashkovich**

Constructing extended formulations using polyhedral relations

**Coauthor: Volker Kaibel**

**Abstract:**

There are many examples of optimization problems whose associated

polyhedra can be described much nicer, and with way less inequalities, by projections of higher dimensional polyhedra than this would be possible in the original space. However, currently not many general tools to construct such extended formulations are available. Here, we develop a framework of polyhedral relations that generalizes inductive constructions of extended formulations via projections, and we particularly elaborate on the special case of reflection relations. The latter ones provide polynomial size extended formulations for several

polytopes that can be constructed as convex hulls of the unions of (exponentially) many copies of an input polytope obtained via sequences of reflections at hyperplanes. We demonstrate the use of the framework by deriving small extended formulations for the *G*-permutahedra of all finite reflection groups *G* (generalizing both Goeman's extended formulation of the permutahedron of size *O(n **log* n) and Ben-Tal and Nemirovski's extended formulation with *O(k)* inequalities for the regular *2k*-gon) and for Huffman-polytopes (the convex hulls

of the weight-vectors of Huffman codes).

**Wednesday, 11:30 - 11:55 h, Room: H 3004, Talk 3**

**Dirk Oliver Theis**

Some lower bounds on sizes of positive semidefinite extended formulations

**Coauthor: Troy Lee**

**Abstract:**

Among other, similar, statements, we prove the following:

\

*Theorem.* *Every positive semidefinite extended*

formulation for the Cut polytope of *K*_{n} dominating the 3-clique inequalities must have size at *Ω(n*^{2}).

\

(The size of a positive semidefinite formulation is the dimension of

the positive semidefinite matrices.) This contrasts the fact that the

famous Goemans-Williamson relaxation has linear size: It dominates

only a weakened form of the *3*-clique inequalities.