<p>An <em>extended formulation</em> (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a linear system</p>

<p>\begin{equation}
\label{equation:ExtForm}
Ex + Fy  = g, y\geq 0
\end{equation}</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>Thus the formulation you described in your question seems to be incorrect.
In special the right side of the inequality is expected to be a vector and not
a number.</p>

<p>I believe that the way in which you represent strings as extremal points of a
polytope is somewhat arbitrary. But a sort of canonical way is to represent
a string $x$ over $\{0,1\}^n$ by a vector $v\in \mathbb{R}^n$  such that
$v_i=x_i$.</p>

<p>However these extremal points are usually meant to represent the solutions to
a given combinatorial problem. For instance, in the cut polytope is the convex hull
the characteristic vectors of all cuts in the complete graph $K_n=(V_n,E_n)$:</p>

<p>\begin{equation}
\label{equation:CutPolytope}
CUT(n) = conv\{ \chi^{\delta(X)\in \mathbb{R}^{E_n}} | X\subseteq V_n\}
\end{equation}</p>

<p>where $\delta(X)$ is the set of edges from $X$ to its complement $\overline{X}$.
Similarly, the <em>stable set polytope</em> is the convex hull of the vectors corresponding
to the characteristic functions of all stable sets of $G$.</p>

<p>\begin{equation}
\label{equation:StableSet}
STAB(G) = conv\{\chi^S \in \mathbb{R}^V | S \mbox{ is a stable set of $G$}\}
\end{equation}</p>

<p>The TSP polytope $TSP(n)$ is the convex hull of all vectors corresponding to the characteristic functions of sets of edges representing the tours in $K_n$:</p>

<p>\begin{equation}
\label{equation:TSP}
TSP(n) = conv\{\chi^F \in \mathbb{R}^{E_n} | F\subseteq E_n \mbox{ is a tour of } K_n\}
\end{equation}</p>

<p>The interest on extended formulations stems from the fact that some polytopes,
such as the Permutahedron,which have an exponential number of facets admit extended formulations with a polynomial number of inequalities. However, recently <a href="http://arxiv.org/abs/1111.0837" rel="nofollow">Fiorini, Massar, Pokutta, Tiwary and De Wolf</a> proved that any extended formulation of any of the three polytopes described above require an exponential number of innequalities.</p>

CC BY-SA 3.0
2013-03-24T12:01:54.273Z
Mateus,Thanks!Your answer is "YES, but exponential linear constraints for several NP-solutions are unavoidable", is'nt you ?
echuly
CC BY-SA 3.0
2013-03-24T12:11:34.773Z
In your formulation $Ex + Fy  = g, y\geq 0$,equality and $y\geq 0$ is contained.Is equality and $y\geq 0$ necessary ?
echuly
CC BY-SA 3.0
2013-03-24T13:18:14.310Z
The answer to your question is no, since you are writing $Ax + By \geq d$  and the right hand side of the inneq. has nothing to do with the dimension of $y$. The equality and the $\geq 0$ are without loss of generality, since any extended formulation can be put in this form without changing the number of innequalities (See "slack form" http://en.wikipedia.org/wiki/Linear_programming). But this fact is far from being research level. If you want to see explicit formulations of polytopes I would point to http://eprints.lse.ac.uk/31670/
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2013-03-25T02:14:12.773Z
Sorry....of course, I know the notion of "slack".
echuly
CC BY-SA 3.0
2013-03-24T11:52:47.170Z
2013-03-24T11:52:47.170Z
Mateus de Oliveira Oliveira
<p>Extended Formulation of a polytope <span class="math-container">$P \subseteq \mathbb{R}$</span> is a system of linear constraints which satisfies the following condition:</p>
<p><span class="math-container">$x \in P \iff \exists y\in \mathbb{R}^{d} \mbox{ such that } Ax + By \geq d$</span></p>
<p>A convex set of <span class="math-container">$n$</span>-points <span class="math-container">$x_{1},...,x_{n}$</span> in <span class="math-container">$\mathbb{R}^{d}$</span> is defined as <span class="math-container">$\mbox{conv}(\{x_{1},...,x_{n}\})=\{y\in \mathbb{R}^{n}  |y=c_{1}x_{1}+c_{2}x_{2}+\cdots +c_{n}x_{n}, c_{1}+c_{2}+\cdots +c_{n}=1   \}$</span></p>
<h1>Question:</h1>
<p>Is the following statement true ?</p>
<p>Statement:
For every <span class="math-container">$P\subseteq  \{0,1\}^{n}$</span>, If we construct a system of linear constraints <span class="math-container">$ Ax + By \geq d,x\in \mathbb{R}^{n},y\in \mathbb{R}^{d}$</span> such that</p>
<p><span class="math-container">$x \in P \iff \exists y\in \mathbb{R}^{d} \mbox{ such that } Ax + By \geq d$</span></p>
<p>,then the system of linear constraints <span class="math-container">$ Ax + By \geq d,x\in \mathbb{R}^{n},y\in \mathbb{R}^{d}$</span> is a extended formulation of <span class="math-container">$\mbox{conv}  (P)$</span>  ?</p>
<p>I am not sure about expressing a set of boolean strings by linear constraints.</p>

<cc.complexity-theory><linear-programming><boolean-functions><convex-geometry>
Expressing a set of 0-1 strings by Extended Formulation
echuly
# Expressing a set of 0-1 strings by Extended Formulation

(Asked by: username_0 on 2013-03-24)

Extended Formulation of a polytope $P \subseteq \mathbb{R}$ is a system of linear constraints which satisfies the following condition:

$x \in P \iff \exists y\in \mathbb{R}^{d} \mbox{ such that } Ax + By \geq d$

A convex set of $n$-points $x\_{1},...,x\_{n}$ in $\mathbb{R}^{d}$ is defined as $\mbox{conv}(\{x\_{1},...,x\_{n}\})=\{y\in \mathbb{R}^{n} |y=c\_{1}x\_{1}+c\_{2}x\_{2}+\cdots +c\_{n}x\_{n}, c\_{1}+c\_{2}+\cdots +c\_{n}=1 \}$

# Question:

Is the following statement true ?

Statement:
For every $P\subseteq \{0,1\}^{n}$, If we construct a system of linear constraints $ Ax + By \geq d,x\in \mathbb{R}^{n},y\in \mathbb{R}^{d}$ such that

$x \in P \iff \exists y\in \mathbb{R}^{d} \mbox{ such that } Ax + By \geq d$

,then the system of linear constraints $ Ax + By \geq d,x\in \mathbb{R}^{n},y\in \mathbb{R}^{d}$ is a extended formulation of $\mbox{conv} (P)$ ?

I am not sure about expressing a set of boolean strings by linear constraints.

**Tags:** cc.complexity-theory, linear-programming, boolean-functions, convex-geometry


---

## 1 answers

### Answer by username_1 on 2013-03-24. Score: 1

An *extended formulation* (EF) of a polytope $P\subseteq \mathbb{R}^d$ is a linear system

\begin{equation}
\label{equation:ExtForm}
Ex + Fy = g, y\geq 0
\end{equation}

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.

Thus the formulation you described in your question seems to be incorrect.
In special the right side of the inequality is expected to be a vector and not
a number.

I believe that the way in which you represent strings as extremal points of a
polytope is somewhat arbitrary. But a sort of canonical way is to represent
a string $x$ over $\{0,1\}^n$ by a vector $v\in \mathbb{R}^n$ such that
$v\_i=x\_i$.

However these extremal points are usually meant to represent the solutions to
a given combinatorial problem. For instance, in the cut polytope is the convex hull
the characteristic vectors of all cuts in the complete graph $K\_n=(V\_n,E\_n)$:

\begin{equation}
\label{equation:CutPolytope}
CUT(n) = conv\{ \chi^{\delta(X)\in \mathbb{R}^{E\_n}} | X\subseteq V\_n\}
\end{equation}

where $\delta(X)$ is the set of edges from $X$ to its complement $\overline{X}$.
Similarly, the *stable set polytope* is the convex hull of the vectors corresponding
to the characteristic functions of all stable sets of $G$.

\begin{equation}
\label{equation:StableSet}
STAB(G) = conv\{\chi^S \in \mathbb{R}^V | S \mbox{ is a stable set of $G$}\}
\end{equation}

The TSP polytope $TSP(n)$ is the convex hull of all vectors corresponding to the characteristic functions of sets of edges representing the tours in $K\_n$:

\begin{equation}
\label{equation:TSP}
TSP(n) = conv\{\chi^F \in \mathbb{R}^{E\_n} | F\subseteq E\_n \mbox{ is a tour of } K\_n\}
\end{equation}

The interest on extended formulations stems from the fact that some polytopes,
such as the Permutahedron,which have an exponential number of facets admit extended formulations with a polynomial number of inequalities. However, recently [Fiorini, Massar, Pokutta, Tiwary and De Wolf](http://arxiv.org/abs/1111.0837) proved that any extended formulation of any of the three polytopes described above require an exponential number of innequalities.

> **Comments:**
> **username_0**: Mateus,Thanks!Your answer is "YES, but exponential linear constraints for several NP-solutions are unavoidable", is'nt you ?  
> **username_0**: In your formulation $Ex + Fy  = g, y\geq 0$,equality and $y\geq 0$ is contained.Is equality and $y\geq 0$ necessary ?  
> **username_1**: The answer to your question is no, since you are writing $Ax + By \geq d$  and the right hand side of the inneq. has nothing to do with the dimension of $y$. The equality and the $\geq 0$ are without loss of generality, since any extended formulation can be put in this form without changing the number of innequalities (See "slack form" http://en.wikipedia.org/wiki/Linear_programming). But this fact is far from being research level. If you want to see explicit formulations of polytopes I would point to http://eprints.lse.ac.uk/31670/  
> **username_0**: Sorry....of course, I know the notion of "slack".  

---

