Greed Is Slow on Sparse Graphs of Oriented Valued Constraints

We cannot hope for a polynomial time algorithm to solve arbitrary combinatorial optimization problems. But we still need to try to do something to solve these hard problems. Given that many hard problems can be defined as finding an assignment $x\in {\{0,1\}}^n$ that maximizes some pseudo-Boolean function – that we call a fitness function – many turn to local search as a heuristic method [1]. Local search methods start at an initial assignment, then apply a fixed update rule to select a better adjacent assignment to move to until no further improvement is possible. Such a sequence of adjacent improving assignments is called an ascent. One of the most popular update rules is to always select the adjacent assignment that increases fitness by the largest amount, that is, to follow the steepest ascent– this update rule defines greedy local search [22]. Since greed is just one of many possible update rules, a natural question arises: is greed good? Or more specifically: is greedy local search fast or slow compared to other local search methods?

Since no local search method will be able to solve all instances of hard combinatorial optimization problems in a polynomial number of steps, we need a more nuanced criterium for what makes a local search method fast or slow. We find this nuance in looking at the performance of our methods on subsets of instances of differing simplicity instead of on all instances. Now, if a method cannot solve particularly simple sets of instances in a polynomial number of steps – at least when compared to other similar methods – then we call it slow.

To define our set of all instances and refine that to simple instances, we turn to valued constraint satisfaction problems ($\mathrm{𝖵𝖢𝖲𝖯}$s). In the language of constraint programming, finding the maximum of a pseudo-Boolean function is the same as solving a Boolean $\mathrm{𝖵𝖢𝖲𝖯}$. Given that even binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s can express both $\mathrm{𝖭𝖯}$-hard and $\mathrm{𝖯𝖫𝖲}$-complete problems [3, 11], we define – in Section 2 – our set of all instances as the set of all binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s. Each binary $\mathrm{𝖵𝖢𝖲𝖯}$ can be interpreted as defining a constraint graph with an edge between any two variables that share a constraint. This allows us to use the sparsity of the resulting graphs as a measure of simplicity: we focus on sets of instances of bounded degree and of bounded treewidth or – more restrictively – pathwidth.

In terms of degree, Elsässer and Tscheuschner [8] showed that binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s are $\mathrm{𝖯𝖫𝖲}$-complete under tight reductions even if the constraints are restricted to $\mathrm{𝖬𝖠𝖷𝖢𝖴𝖳}$. The tight $\mathrm{𝖯𝖫𝖲}$-reduction means that there are degree $5$ instances where all ascents are exponential – including the steepest ascent taken by greedy local search. Monien and Tscheuschner [17] constructed a family of instances of degree $4$ for which they claim all ascents are exponential. Finally, all ascents are quadratic when the constraint graph has maximum degree $2$ (Theorem 5.6 in Kaznatcheev [13]). Taken together, this only leaves open the question of efficiency of greedy local search for binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s of degree $3$.

Treewidth as a sparsity parameter has a more complicated – and perhaps more interesting – relationship to the efficiency of local search. There exists a polynomial time non-local search algorithm for finding not just a local maximum but the global maximum for $\mathrm{𝖵𝖢𝖲𝖯}$s of bounded treewidth [2, 4]. Thus, binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s of bounded treewidth are not hard for $\mathrm{𝖯𝖫𝖲}$. Unlike bounded degree, bounded treewidth instances really are a class of simple instances. But the existence of a polynomial-time non-local search algorithm for solving bounded treewidth $\mathrm{𝖵𝖢𝖲𝖯}$s, does not mean that local search will be efficient at finding even a local peak. Cohen et al. [5] have already shown that greedy local search requires an exponential number of steps for Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s of pathwidth $7$. The simplest set of instances on which greedy local search fails was subsequently lowered to pathwidth $4$ [15]. Recently, Kaznatcheev and Vazquez Alferez [16] showed that an old construction of Hopfield networks by Haken and Luby [9] provides a binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$ of pathwidth $3$ on which greedy local search takes an exponential number of steps. Since Kaznatcheev, Cohen and Jeavons [14] have shown that all local search methods will take at most a quadratic number of steps on tree-structured binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s (i.e., treewidth $1$), this leaves only the case of treewidth $2$ as open for the question of whether greedy local search is fast or slow.

There are partial results for these two open questions on degree and treewidth – mostly focused on all or some ascents, rather than steepest ascents – but they cannot be further extended. Poljak [18] showed that if the $\mathrm{𝖵𝖢𝖲𝖯}$ instance is allowed only $\mathrm{𝖬𝖠𝖷𝖢𝖴𝖳}$ constraints then for degree $3$ instances, all ascents are quadratic. However, Poljak’s [18] technique of rewriting degree $3$ $\mathrm{𝖬𝖠𝖷𝖢𝖴𝖳}$ constrain graphs by instances with small weights cannot extend to arbitrary binary constraints. There are degree $3$ $\mathrm{𝖵𝖢𝖲𝖯}$-instances that require exponentially large weights (Example 5.10 in Kaznatcheev [13]) and, in their Example 7.2, Kaznatcheev, Cohen and Jeavons [14] gave an explicit family of instances with max degree $3$ where some ascents are exponential. Similarly, the encouragement-path proof techniques for showing that all local search methods are efficient on $\mathrm{𝖵𝖢𝖲𝖯}$s of treewidth $1$ [14] cannot be extended to treewidth $2$. Specifically, Kaznatcheev, Cohen and Jeavons [14]’s Example 7.2 not only has maximum degree $3$ but also pathwidth $2$. However, although some ascents are exponentially long in this family of instances, the steepest ascents are all short and greedy local search can find the peak in a linear number of steps. More generally, Kaznatcheev and van Marle [15] optimistically conjectured that on any family of $\mathrm{𝖵𝖢𝖲𝖯}$-instances of pathwidth $2$, greedy local search will take at most a polynomial number of steps.

In this paper, we resolve these two open questions on the efficiency of greedy local search for $\mathrm{𝖵𝖢𝖲𝖯}$-instances of degree $3$ and treewidth $2$.¹¹1 In parallel work to ours, van Marle [21] developed a similar construction of exponential steepest ascent. His construction has the same constraint graph – with degree $3$ and pathwidth $2$ – but slightly different weights. The key difference is a much more involved proof of exponential steepest ascents: van Marle [21] shows how to simulate a particular prior construction of some exponential ascent as a steepest ascent on a “padded” instance. This is similar to the prior approaches taken by Cohen et al. [5] and Kazntcheev and van Marle [15]. In contrast, we focus on how to compose individual gadget’s fitness landscapes and their steepest (partial) ascents rather than introducing new subgadgets for simulating whole ascents. We find our approach simpler, and think that future work can more easily generalize our approach to other local search methods. In Section 3, we construct $\mathrm{𝖵𝖢𝖲𝖯}$-instances ${𝒞}_{n,\le n}^{\pm }$ on $6n$ Boolean variables with $7n-1$ binary constraints and $6n$ unary constraints with a constraint graph of maximum degree $3$ and pathwidth $2$ (Proposition 3). In Section 4, we show that greedy local search takes $7(2^n-1)$ steps to solve these simple $\mathrm{𝖵𝖢𝖲𝖯}$-instances (Theorem 6). We construct ${𝒞}_{n,\le m}^{\pm }$ as a path of $m$ gadgets ${𝒞}_{n,m}^{\pm },{𝒞}_{n,m-1}^{-},\mathrm{\dots },{𝒞}_{n,2}^{-},{𝒞}_{n,1}^{-}$ with consecutive gadgets joined by a single binary constraint. Our proof of long steepest ascents is by induction on the number of gadgets in the path. We show that the steepest ascent first flips bits only in the first gadget ${𝒞}_{n,m}^{\pm }$ until it flips the variable that participates in the binary constraint linking ${𝒞}_{n,m}^{\pm }$ to ${𝒞}_{n,m-1}^{-}$. When this linking variable flips to $1$ this gives us the inductive hypothesis of ${𝒞}_{n,\le m-1}^{+}$ and when it flips to $0$, it gives the inductive hypothesis of ${𝒞}_{n,\le m-1}^{-}$. The constraint weights in the gadget are chosen in such a way that after this linking variable is flipped, the next potential flip in ${𝒞}_{n,m}^{\pm }$ increases fitness by a lower amount than the flips in ${𝒞}_{n,\le m-1}^{\pm }$. Thus the steepest ascent continues in the part of the $\mathrm{𝖵𝖢𝖲𝖯}$ corresponding to the inductive hypothesis for $7(2^{m-1}-1)$ steps, until it reaches the local peak of the sub-instance and finally allows flips to continue in ${𝒞}_{n,m}^{\pm }$ that eventually result in the linking variable flipping back, repeating the recursive process for a second time.

We also show that our $\mathrm{𝖵𝖢𝖲𝖯}$-instances are what Kaznatcheev and Vazquez Alferez [16] defined as “oriented” (Proposition 4). This means that the exponential running time of greedy local search on our instances stands in stark contrast to many other non-greedy local search methods that Kaznatcheev and Vazquez Alferez [16] have shown to take a quadratic or fewer steps to solve oriented $\mathrm{𝖵𝖢𝖲𝖯}$s. From this we conclude that among local search methods, greed is particularly slow.

Given some finite set $V$ of variable indexes with size $|V|=d$,²²2Most often this is $V=[d]$, but in our construction of ${𝒞}_{n,\le m}^{\pm }$ in Section 3 it will be $V=[m]\times [6]$. an assignment is a $d$-dimensional Boolean vector $x\in {\{0,1\}}^d$. For every $i\in V$, $x_i$ refers to the $i$th entry of $x$. To refer to a substring with variable indexes $S\subseteq V$, we write the partial assignment $x[S]\in {\{0,1\}}^S$. To complete a partial assignment, we write $x\in {\{0,1\}}^{S}y[V\setminus S]$ to mean that $x_i=y_i$ for $i\in V\setminus S$ and free otherwise. When assignments are sufficiently short we give $x$ and $y$ explicitly, for example, $x_{1}0x_3$ refers to an assignment to $3$ variables where the second variable is set to $0$. If we want to change just the assignment $x_i$ at index $i$ to a value $b\in \{0,1\}$ then we will write $x[i:b]$. Two assignments are adjacent if they differ on a single variable. Or more formally: $x,y\in {\{0,1\}}^d$ are adjacent if there exists an index $i\in [d]$ such that $y=x[i:\overline{x_i}]$, where $\overline{x_i}=1-x_i$.

A fitness landscape is any pseudo-Boolean function $f:{\{0,1\}}^V\to \mathbb{Z}$ together with the above notion of adjacent assignments. Given any $S\subseteq V$, the sublandscape on $S$ given background $y\in {\{0,1\}}^{V\setminus S}$ is the function $f$ restricted to inputs $x\in {\{0,1\}}^{S}y[V\setminus S]$. An assignment $x$ is called a local peak in a fitness landscape if $f(x)\ge f(y)$ for all $y$ adjacent to $x$. A sequence of assignments $x^0,x^1,\mathrm{\dots },x^T$ is called an ascent in the fitness landscape if $x^{t-1}$ and $x^t$ are adjacent for all $t\in [T]$, , and $x^T$ is a local peak. An ascent is called a steepest ascent, if for all $t\in [T]$ and all assignments $y$ adjacent to $x^{t-1}$ it is the case that $f(x^t)\ge f(y)$. Any local search method (that only takes increasing steps) follows an ascent. Greedy local search follows a steepest ascent.

A binary Boolean valued constraint satisfaction problem ($\mathrm{𝖵𝖢𝖲𝖯}$) on $d$ Boolean variables with indexes in $V$ is a set of constraints $𝒞=\{c_S\}$. Each constraint is a weight $c_S\in \mathbb{Z}\setminus \{0\}$ with an associated scope $S\subseteq V$ of size $|S|\le 2$. We say that $c_S$ is a unary constraint if $|S|=1$, and a binary constraint if $|S|=2$. Overloading notation, the set of constraint $𝒞$ implements a pseudo-Boolean function $𝒞:{\{0,1\}}^d\to \mathbb{Z}$ that we call the fitness function:

Solving $𝒞$ means finding an assignment $x$, that maximizes the fitness function $𝒞(x)$. ³³3 One could also consider a $\mathrm{𝖵𝖢𝖲𝖯}$-instance as a set of constraints $\widehat{𝒞}=\{C_S\}$ where each $C_S:{\{0,1\}}^S\to \mathbb{Z}$ is a binary function. This formulation is equivalent to our formulation above because an arbitrary constraint with scope $S$ can be expressed as a polynomial. For example, take $S=\{i,j\}$: $C_S(x_i,x_j)$ $=C_S(0,0)(1-x_i)(1-x_j)+C_S(1,0)x_i(1-x_j)+C_S(0,1)(1-x_i)x_j+C_S(1,1)x_i{x}_j$ $=C_S(0,0)+(C_S(1,0)-C_S(0,0))x_i+(C_S(0,1)-C_S(0,0))x_j$ $+(C_S(1,1)-C_S(0,1)-C_S(1,0)+C_S(0,0))x_i{x}_j$ The second equality groups alike monomials. One can convert from the $\widehat{𝒞}$ formulation to the $𝒞$ formulation by summing alike monomial terms across all the constraints. That is, the constant terms $C_S(0,0)$ are aggregated into $c_{\mathrm{\varnothing }}$, all the $C_{\{i,\mathrm{\_}\}}$ (i.e., coefficients appearing before $x_i$) aggregate into $c_i$, and $c_{\{i,j\}}=C_{\{i,j\}}(1,1)-C_{\{i,j\}}(0,1)-C_{\{i,j\}}(1,0)+C_{\{i,j\}}(0,0)$ (i.e., coefficient appearing before $x_i{x}_j$). It takes linear time to covert from $\widehat{𝒞}$ to $𝒞$ (see Theorem 3.4 in Kaznatcheev, Cohen and Jeavons [14]).

When discussing graph-theoretical properties of $𝒞$, we treat the scopes of binary constraints as edges. So $V(𝒞)=V$ and $E(𝒞)=\{i,j|i\ne j\text{ and }{c}_{\{i,j\}}\in 𝒞\}$ is the set of scopes of the binary constraints of $𝒞$. For each variable index $i\in V$, we define the neighbourhood $N_{𝒞}(i)=\{j|i,j\in E(𝒞)\}$ as the set of variable indexes in $V\setminus \{i\}$ that appear in a constraint with $i$. In this paper, we measure the simplicity of a $\mathrm{𝖵𝖢𝖲𝖯}$-instance $𝒞$ by the maximum degree and by the pathwidth of its constraint graph. Given a graph $G=(V,E)$, the pathwidth of $G$ is the minimum possible width of a path decomposition of $G$. A path decomposition of $G$ is a sequence of sets $P=\{X_1,X_2,\mathrm{\dots },X_p\}$ where $X_r\subset V(G)$ for $r\in [p]$ with the following three properties:

1. 1.

   Every vertex $v\in V(G)$ is in at least one set $X_r$.

2. 2.

   For every edge $\{u,v\}\in E(G)$ there exists an $r\in [p]$ such that $X_r$ contains both $u$ and $v$.

3. 3.

   For every vertex $v\in V(G)$, if $v\in X_r\cap X_s$ then $u\in X_{\mathrm{\ell }}$ for all $\mathrm{\ell }$ such that $r\le \mathrm{\ell }\le s$.

The width of a path decomposition is defined as ${\max }_{X_r\in P}|X_r|-1$. We refer the reader to [6] for more details and for the definition of treewidth, and to [7] for standard graph terminology.

It is often useful to see how the value of the fitness function $𝒞$ changes when a single variable is modified. In particular, we denote with ${\nabla }_i𝒞(x)=𝒞(x[i:1])-𝒞(x[i:0])$ the fitness change associated with changing variable $x_i=0$ to $x_i=1$ given some background assignment $x$. It is easy to see that ${\nabla }_i𝒞(x)=c_i+{\sum }_{j\in N_{𝒞}(i)}{c}_{\{i,j\}}{x}_j$, and the value of ${\nabla }_i𝒞(x)$ depends only on the assignment to variables with indexes in $N_{𝒞}(i)$. We use this to overload ${\nabla }_i𝒞$ to partial assignments: if $y\in {\{0,1\}}^{N(i)}$ we consider ${\nabla }_i𝒞(y)$ to be well defined.

We say that $x_i$ has preferred assignment $1$ in background $x$ if ${\nabla }_i𝒞(x)>0$ and preferred assignment $0$ in background $x$ if .

In other words, Definition 1 tells us that if $i$ sign-depends on $j$, the preferred assignment of variable $x_i$ depends on the assignment to variable $x_j$.

The constraint graphs of oriented $\mathrm{𝖵𝖢𝖲𝖯}$s have no directed cycles [16]. Thus, if $y$ is any assignment to the first $k$ variables of a topological ordering of the variables of an oriented constraint graph, then $k$ is sign-independent given background $y$. In other words, if $𝒞$ is oriented, there is an ordering on the variables such that later variables are conditionally-independent of earlier ones. This implies that the fitness landscape of $𝒞$ is single peaked on every sublandscape [16]. Depending on the research community, such landscapes are known as semismooth fitness landscapes [12, 16], completely unimodal pseudo-Boolean functions [10], or acyclic unique-sink orientations of the hypercube [19, 20]. Given that fitness landscapes implemented by oriented $\mathrm{𝖵𝖢𝖲𝖯}$s are single-peaked, we use $x^{\ast }(𝒞)$ to denote the peak of the landscape implemented by the oriented $\mathrm{𝖵𝖢𝖲𝖯}$-instance $𝒞$.

Given two parameters $1\le m\le n$, in this section, we construct the $\mathrm{𝖵𝖢𝖲𝖯}$-instances ${𝒞}_{n,\le m}^{+}$ and ${𝒞}_{n,\le m}^{-}$ on $6m$ variables and, in Section 4, show that they both have a steepest ascent of length $7(2^m-1)$. We construct the ${𝒞}_{n,\le m}^{\pm }$ as a path of $m$ gadgets ${𝒞}_{n,m}^{\pm },{𝒞}_{n,m-1}^{-},\mathrm{\dots },{𝒞}_{n,2}^{-},{𝒞}_{n,1}^{-}$ where each gadget ${𝒞}_{n,k}^{\pm }$ is defined on $6$ variables $V_k=\{(k,i)|\mathrm{\hspace{0.33em}1}\le i\le 6\}$. For notational convenience, we define $V_{\le m}:={\cup }_{k=1}^m{V}_k$. Note that the two $\mathrm{𝖵𝖢𝖲𝖯}$s are exactly the same except on the $m$th gadget where ${𝒞}_{n,\le m}^{+}$ has ${𝒞}_{n,m}^{+}$ and ${𝒞}_{n,\le m}^{-}$ has ${𝒞}_{n,m}^{-}$. We will present the construction of the gadgets ${𝒞}_{n,k}^{\pm }$ in two stages. First, we will define the scopes of all the constraints to get the constraint graph and show that these constraint graphs are very sparse (Proposition 3). Second, we will assign weights to the constraints and show that the $\mathrm{𝖵𝖢𝖲𝖯}$s are oriented (Proposition 4).

Both the ${𝒞}_{n,k}^{-}$ and ${𝒞}_{n,k}^{+}$ gadgets have all six unary constraints and the same six binary constraints with scopes $\{(k,1),(k,2)\}$, $\{(k,2),(k,3)\}$, $\{(k,3),(k,6)\}$, $\{(k,1),(k,4)\}$, $\{(k,4),(k,5)\}$, $\{(k,5),(k,6)\}$. Finally, we connect adjacent gadgets with a single binary constraint with scope $\{(k,6),(k-1,1)\}$. The constraint graph of ${𝒞}_{n,k}^{-}$ along with the connections to the adjacent gadgets at $k+1$ and $k-1$ are shown in Figure 1. It is not hard to check based on the above definition that the constraint graphs of ${𝒞}_{n,\le m}^{\pm }$ are sparse:

We can now show that it takes a large number of steps to go from the assignment $x^{\ast }({𝒞}_{n,\le m}^{-})=0^{6m}$ to the peak $x^{\ast }({𝒞}_{n,\le m}^{+})={1111100}^{6(m-1)}$ in the semismooth fitness landscape implemented by ${𝒞}_{n,\le m}^{+}$ (and vice versa for the landscape implemented by ${𝒞}_{n,\le m}^{-}$):

There are two important structural features of our construction: that it is sparse (Proposition 3) and that is is oriented (Proposition 4). Sparseness resolves in the negative the two open questions on the efficiency of greedy local search for $\mathrm{𝖵𝖢𝖲𝖯}$-instances of degree $3$ and treewidth $2$. Given that all ascents are short for $\mathrm{𝖵𝖢𝖲𝖯}$s of degree $2$ [13] and treewidth $1$ [14], the ${𝒞}_{n,\le n}^{\pm }$ family of instances that are hard for greedy local search belong to the simplest class of instances where some local search has the possibility to fail. That ${𝒞}_{n,\le n}^{\pm }$ is an oriented $\mathrm{𝖵𝖢𝖲𝖯}$ (Proposition 4), reminds us that this failure of greedy local search is not due to the popular suspect of “bad” local peaks blocking the way to a hard to find global peak. Oriented $\mathrm{𝖵𝖢𝖲𝖯}$s only produce semismooth fitness landscapes that are single peaked on each sublandscape [16]: there are no “bad” local peaks in this family of instances, there is the single global peak. Further, in semismooth fitness landscapes, there is always a short ascent of Hamming distance from any initial assignments to unique peak [10, 12]. A short ascents is always available in ${𝒞}_{n,\le n}^{\pm }$, but greed stops us from find it.