Expressing a set of 0-1 strings by Extended Formulation

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.

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 proved that any extended formulation of any of the three polytopes described above require an exponential number of innequalities.

• Mateus,Thanks!Your answer is "YES, but exponential linear constraints for several NP-solutions are unavoidable", is'nt you ? Mar 24 '13 at 12:01
• In your formulation $Ex + Fy = g, y\geq 0$,equality and $y\geq 0$ is contained.Is equality and $y\geq 0$ necessary ? Mar 24 '13 at 12:11
• 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" 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 eprints.lse.ac.uk/31670 Mar 24 '13 at 13:18
• Sorry....of course, I know the notion of "slack". Mar 25 '13 at 2:14