# Extended Formulaiton and Integer Programming

An extended formulation (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a system of linear constraints $Ex + Fy = g, y\geq 0$

in variables $(x,y)\in \mathbb{R}^{d+r}$ where $E,F$ are real matrices with $d,r$ columns respectively and $g$ is a column vector such that $x\in P$ if and only if there exists $y$ such that the equation above holds.

size of the EF is the number of linear constraints.

$P_{\mbox{spanning tree}}(G) = conv\{ \chi^{E(T)} \in \mathbb{R}^{E} : T \mbox{ is a spanning tree of }G \}.$

It is known that this polytope has the following formulation.

$x(E[U]) \leq |U| -1$ for nonempty $U \subseteq V$, $x(E) = |V|-1$, $x_e > 0$ for $e\in E$

It is also known that the optimal solution of the following LP is 0-1 vector and the EF of spanning tree polytope has the size $O(n^{3}),n$is the size of the vertex set.

minmize:$\sum_{e \in E} c_{e}x_{e}$

subject to:

$x(E[U]) \leq |U| -1$ for nonempty $U \subseteq V$,

$x(E) = |V|-1$,

$x_e > 0$ for $e\in E$

# Q1

Combining the above facts, does the folowing statement hold ?

Statement:

There is the foloowing system of $O(n^{3})$ linear constraints

$\sum_{e \in E} 1\cdot x_{e}\geq |V|-1$

$Ex + Fy = g, y\geq 0$,

and it holds that $x\in \mathbb{R}^{d}$ satisfies the above linear constraints $\iff$ $x\in \{0,1 \}^{d}$

# Q2

Is the significance of the notion of EF that the small size linear programming relaxation of 0-1 integer programming which solves some combinatorial problems can compute exact integer solution?

# Q3

Recently [Fiorini, Massar, Pokutta, Tiwary and De Wolf][1] proved that any extended formulation of any of the three polytopes described above require an exponential number of innequalities. [1]: http://arxiv.org/abs/1111.0837

Does this result means that small size LP relaxation of 0-1 integer programming which solves the $NP-complete$ problems can $not$ compute exact integer solution ?

• Q2: yes; there are also generalizations of extended formulations that deal with integrality gaps and approximating solutions – Sasho Nikolov Apr 5 '13 at 14:55
• Q1: No. Typically you represent the convex hull of integer feasible points. Any convex combination of two points will satisfy the constraints, but it may not be 0-1. – Austin Buchanan Apr 6 '13 at 16:47