Pure DP versus LP algorithms

A linear program (LP) is a system $Ax\leq b$ of linear inequalities, where $A$ is a $k\times m$ matrix over the reals, and $b\in\RR^k$. In the case of optimization, the problem is, given a (target) vector $c\in\RR^m$, to maximize or minimize $\skal{c,x}$ subject to $Ax\leq b$ and $x\in \RR^m$.

1. Boolean circuits to LPs

Let $\Phi(x)$ be a (non-monotone!) $(\lor,\land,\neg)$ circuit with $s$ gates and $n$ input variables $x_1,\ldots,x_n$ computing a Boolean function $f:\{0,1\}^n\to \{0,1\}$. For convenience, let us call also input variables gates; hence, we have $m=n+s$ gates, the $i$th of which is either an input variable (if $1\leq i\leq n$) or an AND, OR or NOT operation applied to some previous gates. Introduce a variable $x_u$ for each gate $u$ of $\Phi$; hence, if $u=x_i$ for $i\in\{1,\ldots,n\}$, then $x_u=x_i$ is an "old" variable.

• For a NOT gate $w=\neg\, u$ take constraints $0\leq x_w=1-x_u\leq 1$, that is, \begin{align*} -x_w &\leq 0\\ x_w+x_u &\leq 1\\ -x_u-x_w &\leq -1\\\ -x_u &\leq 0\,. \end{align*}
• For an OR gate $w=u\lor v$ take the constraints $0\leq x_u\leq x_w\leq 1$, $0\leq x_v\leq x_w\leq 1$, $x_w\leq x_u+x_v$, that is, \begin{align*} -x_u &\leq 0\\ x_u-x_w &\leq 0\\ x_w & \leq 1\\ -x_v &\leq 0\\ x_v-x_w &\leq 1\\ x_w-x_u-x_v & \leq 0\,. \end{align*}
• For an AND gate $w=u\land v$ take the constraints $0\leq x_w\leq x_u\leq 1$, $0\leq x_w\leq x_v\leq 1$, $x_w\geq x_u+x_v-1$, that is, \begin{align*} -x_w &\leq 0\\ x_w-x_u &\leq 0\\ x_u & \leq 1\\ x_w-x_v &\leq 0\\ x_v & \leq 1\\ x_u+x_v-x_w &\leq 1\,. \end{align*}
• For the output gate $o$ add the constraint $x_o=1$, that is, \begin{align*} x_o &\leq 1\\ -x_o &\leq -1\,. \end{align*}

Let $P=\{(x_1,\ldots,x_n)\colon Ax\leq b, x\in\RR^m\}$ be the projection of the resulting polytope onto the first $n$ positions. It can be verified that, if the first $n$ variables $x_1,\ldots,x_n$ have values $0$ and $1$, then all other variables are forced to have value $0$ or $1$ equal to the output value of the corresponding gate. Let, for example, $w=u\lor v$ be an OR gate. If $x_u=x_v=0$, then $0\leq x_u\leq x_w\leq 1$ gives $x_w\geq 0$, while $x_w\leq x_u+x_v$ gives $x_w\leq 0$; hence, $x_w=0$. If $x_u=1$, then $0\leq x_u\leq x_w\leq 1$ gives $x_w=1$, and similarly when $x_v=1$.

Thus, $P\cap\{0,1\}^n=f^{-1}(1)$. That is, the projection of LP $Ax\leq b$ onto the first $n$ variables includes all $0$-$1$ vectors accepted by the function $f$ and excludes all vectors rejected $f$.

Remark 1: Note the importance of allowing new variables in the resulting LP. Without new variables, linear programming is extremely weak for decision problems; even such trivial Boolean functions as parity require LPs of exponential size.

2. Tropical circuits to LPs

Again, let us call also input variables gates; hence, we have $m=n+s$ gates, the $i$th of which is either an input variable (if $1\leq i\leq n$) or is an addition or a $\min$ operation applied to some previous gates. As before, introduce a variable $x_u$ for each gate $u$ of $\Phi$; hence, if $u=x_i$ for $i\in\{1,\ldots,n\}$, then $x_u=x_i$ is an "old" (input) variable $x_i$ of the circuit $\Phi$.

• For an addition gate $w=u+v$ take the constraint $x_w=x_u+x_v$, that is, the constraints $x_w-x_u-x_v\leq 0$ and $x_u+x_v-x_w\leq 0$.
• For a $\min$ gate $w= \min\{u,v\}$ take the constraints $x_w \leq x_u$ and $x_w \leq x_v$, that is, $x_w-x_u\leq 0$ and $x_w-x_v\leq 0$.

Finally, let the target function be "maximize $x_o,$" where $o$ is the output gate of $\Phi$. That is, in this LP, $b=\vec{0}$ is the all-$0$ vector, and $c$ is a vector with one $1$ in the last position and zeros elsewhere. Now, for any assignment of weights to the variables $x_1, \dots, x_n$, the linear program outputs exactly the value that the $(\min,+)$ circuit $\Phi$ computes: \[ \mbox{$x_w=\min\{x_u,x_v\}$ iff $x_w=\max\{z\colon z\leq x_u, z\leq x_v\}$.} \] A similar construction works for minimizing linear programs and tropical $(\max,+)$ circuits.

Thus, tropical $(\min,+)$ and $(\max,+)$ circuits can be encoded as LPs of almost the same size.

On the other hand, there are problems that can be solved efficiently by an optimizing LP algorithm but not by pure DP $(\min,+)$ or $(\max,+)$ algorithms. For example, the assignment problem (minimum weight perfect matching in $K_{n,n}$ problem) requires tropical circuits of exponential $2^{\Omega(n)}$ size (Theorem 3.6 in the book), but can be solved with only $O(n^3)$ operations by the well-known "Hungarian LP algorithm" of Kuhn [4]. So we can conclude that LP is strictly stronger than pure DP.

This is not surprising. As we have just seen, every Boolean $(\lor,\land,\neg)$ circuit of size $s$ can be represented as a system of linear inequalities with about $s$ variables and about $s$ inequalities. But solving this LP (computing the minimum of maximum values of $\skal{c,x}$) requires very powerful operations like branchings via if-then-else operation. Why this latter operation is really powerful is shown by the following simple example: Boolean negation $\neg x=1-x$ (a "devil" operation prohibiting to capture the power of non-monotone Boolean circuits for decades) is just a seemingly "innocent" operation "if $x=0$ then $1$ else $0$."

Remark 2: Besides the if-then-else constraints, Kuhn's LP algorithm only uses $(\min,+,-)$ operations. Problem 3 in the book asks whether if-then-else constraints can be avoided at least for this particular problem: can the assignment problem be solved by an extended tropical $(\min,+,-)$ circuit (with subtraction gates) of polynomial size. That, sometimes, if-then-else constraints can be avoided is demonstrated in Remark 6.8 of Section 6.2 in the book on the MST problem (minimum weight spanning tree in $K_n$ problem).   $\Box$

Remark 3: In the book, we consider discrete optimization (say, minimization) problems of the form $f(x)=\min_{a\in A}\skal{a,x}$ for given finite sets $A\subseteq\NN^n$ of feasible solutions, and do not care about how the sets $A$ are specified. One way to specify $A$ is to let it be the set $A=\{a\in \NN^n\colon Ma\leq b\}$ of all vectors $a\in\NN^n$ fulfilling all inequalities of the system $Ma\leq b$ of linear inequalities for some $m\times n$ matrix $M$ and a $1\times m$ vector $b$ over the reals. Then the problem $f$ turns into a minimizing LP \[ f(x)=\min\{\skal{c,a}\colon Ma\leq b, a\in\NN^n, c=x\}\,. \] That is, target vectors $c$ are input weightings $x\in\RR_+^n$, and the set $A$ of feasible solutions is the set of integer solutions $a\in\NN^n$ of the given system $Ma\leq b$ of linear inequalities.   $\Box$

3. Digression: LP and extension complexity

Given $A\subseteq\{0,1\}^n$, its separation complexity, $\sep{A}$, is the minimum $\xc{P}$ over all polytopes $P\subseteq\RR^n$ with $P\cap\{0,1\}^n=A$; such a $P$ is called a separating polytope for $A$.

The Valiant-Yannakakis simulation yields the following fact. For a Boolean function $f:\{0,1\}^n\to\{0,1\}$, let $\BBool{f}$ denote the minimum size of a Boolean $(\lor,\land,\neg)$ circuit computing $f$.

Fact 1: Let $A=f^{-1}(1)$. If $\BBool{f}\leq s$ then $\sep{A}=O(n+s)$.

Note that the convex hull $P_f:=\conv{A}$ of the set $A=f^{-1}(1)$ of vectors accepted by a Boolean function $f$ is a separating polytope for $A$. These polytopes are well-studied. The first lower bounds on the extension complexity $\xc{P_f}$ for explicit Boolean functions $f$ were proved already by Yannakakis in his seminal paper [6] under the additional restriction that the extended polytopes $Q$ must be "symmetric" in a particular sense. The breakthrough by Fiorini, Massar, Pokutta, Tiwary, and de Wolf [1] more than twenty years later showed that several well-studied polytopes, including the correlation polytope and the TSP polytope, have exponential extension complexity; without the "symmetry" restriction. The proof used communication complexity arguments; a taste of how this goes can be seen in the short note of Kaibel and Weltge [3]. Rothvoß [4] has shown that the matching polytope also has exponential extension complexity (see references in [1,4] for extensive literature about the extension complexity).

However, $P_f$ is just one of infinitely many separating polytopes for $A=f^{-1}(1)$, and these results do not imply a lower bound on $\sep{f}$. So far, high lower bounds on $\sep{A}$ are only known for non-explicit sets $A\subseteq\{0,1\}^n$. In particular, Hrubeš and Talebanfard [2] have shown that $\sep{A}=O(2^{n/2})$ holds for all $A\subseteq\{0,1\}^n$, and there is a set $A\subseteq\{0,1\}^n$ such that $\sep{A}\geq 2^{\frac{n}{3}(1-o(1)}$.

References:

1. S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf: Exponential lower bounds for polytopes in combinatorial optimization, Journal of the ACM, 62:2 (2015), 17:1-17:23.    arxiv
2. P. Hrubeš and N. Talebanfard: On the extension complexity of polytopes separating subsets of the Boolean cube, Discrete & Computational Geometry, 70 (2023), 268–278.    arxiv
3. V. Kaibel and S. Weltge: A short proof that the extension complexity of the correlation polytope grows exponentially, arXiv preprint arXiv:1307.3543 (to appear in J. Comb. Ser. A)
4. H. W. Kuhn: The Hungarian method for the assignment problem. Naval Research Logistic 2 (1955), 83-97.
5. T. Rothvoß: The matching polytope has exponential extension complexity, Journal of the ACM, 64 (2017) Article 41.    arxiv
6. L. G. Valiant: Reducibility by algebraic projections, L'Enseignement Mathématique, 28 (1982), 253-268.    local copy
7. M. Yannakakis: Expressing combinatorial optimization problems by linear programs, J. Comput. Syst. Sci. 43:3 (1991), 441-466.    local copy