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 $


Combining the above facts, does the folowing statement hold ?


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}$


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?


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 ?

  • 2
    $\begingroup$ Q2: yes; there are also generalizations of extended formulations that deal with integrality gaps and approximating solutions $\endgroup$ – Sasho Nikolov Apr 5 '13 at 14:55
  • 2
    $\begingroup$ 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. $\endgroup$ – Austin Buchanan Apr 6 '13 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.