Invited Session Wed.2.H 3004

Wednesday, 13:15 - 14:45 h, Room: H 3004

Cluster 2: Combinatorial optimization [...]

Extended formulations in discrete optimization III


Chair: Volker Kaibel and Samuel Fiorini



Wednesday, 13:15 - 13:40 h, Room: H 3004, Talk 1

Hans Raj Tiwary
Extended formulations for polygon

Coauthors: Samuel Fiorini, Thomas Rothvoss


The extension complexity of a polytope P is the smallest integer k such that P is the projection of a polytope Q with k facets. We discuss the extension complexity of n-gons in the plane. First, we give a new proof that the extension complexity of regular n-gons is O(log n). Next, we discuss lower bounds for the case when the polygon is not necessarily regular.



Wednesday, 13:45 - 14:10 h, Room: H 3004, Talk 2

Michele Conforti
Extended formulations in mixed-integer programming

Coauthors: Laurence Wolsey, Giacomo Zambelli


We study the convex hull of a mixed-integer set S by expressing each continuous variable as the average of k integral variables.
This allows us to model S as a pure integer set in an extended space.
The integrality of the additional variables allows us to strengthen the inequalities that describe S.
We concentrate on a mixed-integer set defined as follows: Given a bipartite graph G=(U\cup V,E), a set I ⊆ U\cup V and rational numbers bij,,ij ∈ E,
S(G,I)={x ∈ \RU\cup V st xi+xj ≥ bij  ij ∈ E;, xiZ  i ∈ I }.
We show that the set S(G,I) is equivalent to the "network
dual'' set introduced and studied by Conforti, Di Summa,
Eisenbrand and Wolsey. Conforti et al. give an extended formulation for the polyhedron
conv(S(G,I)) and discuss cases in which the formulation is
Our goal is to describe the polyhedron
conv(S(G,I)) in the space of the x variables and we give properties of the facet-defining inequalities.
Our principal result is a characterization of the structure
of facet-defining inequalities when the graph G is a tree.



Wednesday, 14:15 - 14:40 h, Room: H 3004, Talk 3

Giacomo Zambelli
Mixed-integer bipartite vertex covers and mixing sets

Coauthors: Michele Conforti, Bert Gerards, Laurence Wolsey


The mixed-integer bipartite vertex-covering problem consists in optimally assigning weights to the nodes of a bipartite graph so that the sum of the weights on the endnodes of each edge is at least some prescribed edge-requirement, and that the weights on certain nodes are integer. Besides being the natural mixed-integer counterpart of the classical vertex-covering problem, this model arises as a relaxation of
several lot-sizing problems. While no satisfactory polyhedral characterization is known, an extended formulation - albeit not polynomial in size - was given by Conforti, Di Summa, Eisenbrand and Wolsey. We give results on the projection of the extended formulation onto the original space, leading to full polyhedral characterizations for the case when the edge-requirements are half-integral and for certain classes of lot-sizing problems.


  Payday Loans In New Jersey. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.