Exercise 2.20*

Question

Consider the Fourier-Motzkin elimination algorithm.
\begin{enumerate}[label=(\alph*)]
\item Suppose that the number $m$ of constraints defining a polyhedron $P$ is even. Show, by means of an example, that the elimination algorithm may produce a description of the polyhedron $\Pi_{n-1}(P)$ involving as many as $m^{2} / 4$ linear constraints, but no more than that.
\item Show that the elimination algorithm produces a description of the one-dimensional polyhedron $\Pi_{1}(P)$ involving no more than $m^{2^{n-1}} / 2^{2^{n}-2}$ constraints.
\item Let $n=2^{p}+p+2$, where $p$ is a nonnegative integer. Consider a polyhedron in $\Re^{n}$ defined by the $8\left(\begin{array}{l}n \ 3\end{array}ight)$ constraints
$$
\pm x_{i} \pm x_{j} \pm x_{k} \leq 1, \quad 1 \leq i<j<k \leq n
$$
where all possible combinations are present. Show that after $p$ eliminations, we have at least
$$
2^{2^{p}+2}
$$
constraints. (Note that this number increases exponentially with $n .$ )
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item Let $a$ be the number of inequalities of type (2.4), $b$ be the number of inequalities of type (2.5) and $c$ be the number of inequalities of type (2.6). Since we have to make sure that each of the inequalities of type (2.5) is compared to each of the inequalities of type (2.4), the resulting number of constraints in $Q$ is $a \cdot b + c$ (where we have $a,b,c \in \mathfrak{N}:\, a + b + c = m$). We argue that this amount reaches its maximum for $a = b = \frac{m}{2}$ and $c = 0$. \begin{proof} We induct on the original number of constraints $m$.
\begin{itemize}
\item[induction base] For $m=2$ we consider all possible cases of $a+b+c=2$ and obtain
$$\frac{2^2}{4} \geq \left[\begin{array}{ll}
1 \cdot 1 + 0 &= 1\
0 \cdot 1 + 1 &= 1\
1 \cdot 0 + 1 &= 1
\end{array}ight..$$
where in we have not considered the case of two inequalities of type (2.8) as this would result in a trivial projection.
\item[induction step] Now suppose inductively that we have proven this for some $m>2$. We then have, for all $a,b,c \in \mathfrak{N}: a + b + c = m+1$, $c+1
eq m+1$:
$$a + b + c = (a + b + c - 1) + 1 \leq \frac{m^2}{4} + 1 \leq \frac{(m+1)^2}{4}.$$
\end{itemize}

Now we give a very trivial example of the sharpness of the bound in case that $m$ is even.
\begin{example*} Consider the two-dimensional polyhedron with $m=2$ constraints:
$$\left\{\begin{bmatrix} x \ y \end{bmatrix} \ \left| \ 
\begin{bmatrix} 1 & -1 \ -1 & -1 \end{bmatrix} \begin{bmatrix} x \ y \end{bmatrix} \geq \begin{bmatrix} 0 \ -1 \end{bmatrix}ight.ight\}$$
\begin{figure}
\includegraphics[width=0.65	extwidth]{bertsimas_linopt_exercise_2-20_simple.svg}
\caption{Polyhedron defined by $y\geq x$ (red area) and $1-x \geq y$ (blue area) and its projection.} 
\end{figure}
We then obtain inequalities
\begin{equation*}
\left\{\begin{array}{ll}
1-x \geq &y\
&y \geq x
\end{array}ight.
\implies
1-x \geq x,
\end{equation*}
resulting in an unbounded one-dimensional polyhedron $\left(-\infty,\frac{1}{2}ight)$ with $2^2/4 = 1$ constraint.
\end{example*}

\item \begin{proof} We induct on the dimension $n$ of the polyhedron.
\begin{itemize}
\item[induction base] Let $n=2$. Then we only apply the projection once and the assertion follows from part (a) of this exercise.
\item[induction step] Now suppose that we have a polyhedron in $n+1$ dimensions. Applying the Fourier-Motzkin elimination algorithm, we obtain a polyhedron $\Pi_n(P)$ in $n$ dimensions with at most $m^2/4$ constraints. We can apply the induction hypothesis and conclude that the Fourier-Motzkin projection $\Pi_1\left(\Pi_n(P)ight) = \Pi_1(P)$ involves at most
$$\dfrac{\left(\dfrac{m^2}{4}ight)^{2^{n-1}}}{2^{2^n-2}} = \dfrac{m^{2n}}{2^{2^{n+1}-2}}$$
constraints.
\end{itemize}
\end{proof}

\item Applying the previous part to the number of constraints at dimension $n$, we obtain
$$\dfrac{\left[ 8 \cdot {n \choose 3} ight]^{2^p}}{2^{2^{p+1}-2}}
= 2^{\left[3 \cdot 2^p - 2^{p+1} + 2ight]} \cdot {n \choose 3}^{2^p}
= 2^{2^{p} + 2} \cdot {n \choose 3}^{2^p}
\geq 2^{2^p+2}.$$
\end{enumerate}

Exercise 2.20*

Answers

Comments

Exercise 2.20*

Answers

Comments

Add answer