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


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) ∈ Rn × Rq|Bx + Dw ≥ d} and an objective min cTx, we would like to efficiently derive a strong relaxation P={x ∈ Rn | 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 projx(Q),
(v) collectively strong: P is a strong relaxation of projx(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


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


Among other, similar, statements, we prove the following:
Theorem. Every positive semidefinite extended
formulation for the Cut polytope of Kn dominating the 3-clique inequalities must have size at Ω(n2).

(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.


  In particular, Texas Loans Online can cater to the needs of its residents. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.