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

<p>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.</p>

<p><em>size of the EF</em> is the number of linear constraints.</p>

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

<p>It is known that this polytope has the following formulation.</p>

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

<p>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.</p>

<p>minmize:$\sum_{e \in E} c_{e}x_{e}  $</p>

<p>subject to:</p>

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

<p>$x(E) = |V|-1 $,</p>

<p>$x_e &gt; 0 $ for $ e\in E $</p>

<h1>Q1</h1>

<p>Combining the above facts, does the folowing statement hold ?</p>

<p>Statement:</p>

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

<p>$\sum_{e \in E} 1\cdot x_{e}\geq |V|-1$</p>

<p>$Ex + Fy  = g, y\geq 0$, </p>

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

<h1>Q2</h1>

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

<h1>Q3</h1>

<p>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]: <a href="http://arxiv.org/abs/1111.0837" rel="nofollow">http://arxiv.org/abs/1111.0837</a></p>

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

CC BY-SA 3.0
2013-04-05T14:55:08.897Z
Q2: yes; there are also generalizations of extended formulations that deal with integrality gaps and approximating solutions
Sasho Nikolov
CC BY-SA 3.0
2013-04-06T16:47:24.120Z
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
<cc.complexity-theory><boolean-functions><convex-optimization><convex-geometry>
Extended Formulaiton and Integer Programming
echuly
# Extended Formulaiton and Integer Programming

(Asked by: username_0 on 2013-04-05)

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 ?

**Tags:** cc.complexity-theory, boolean-functions, convex-optimization, convex-geometry
> **Comments:**
> **username_1**: Q2: yes; there are also generalizations of extended formulations that deal with integrality gaps and approximating solutions  
> **username_2**: 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.  

---

## 0 answers

