## 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**

**Abstract:**

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**

**Abstract:**

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 *b*_{ij},,ij ∈ E,

let

*S*^{(G,I)}={x ∈ \R^{U\cup V} st x_{i}+x_{j} ≥ b_{ij} ij ∈ E;, x_{i} ∈ **Z** 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

compact.

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**

**Abstract:**

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.