# Evidence of Exponential Speed-Up in the Solution of Hard Optimization Problems

Authors: Fabio L. Traversa; Pietro Cicotti; Forrest Sheldon; Massimiliano Di Ventra
Journal: Complexity
 (2018)

---

## Abstract

Optimization problems pervade essentially every scientific discipline and industry. A common form requires identifying a solution satisfying the maximum number among a set of many conflicting constraints. Often, these problems are particularly difficult to solve, requiring resources that grow exponentially with the size of the problem. Over the past decades, research has focused on developing heuristic approaches that attempt to find an approximation to the solution. However, despite numerous research efforts, in many cases even approximations to the optimal solution are hard to find, as the computational time for further refining a candidate solution also grows exponentially with input size. In this paper, we show anoncombinatorial approach to hard optimization problems that achieves an exponential speed-up and finds better approximations than the current state of the art. First, we map the optimization problem into a Boolean circuit made of specially designed, self-organizing logic gates, which can be built with (nonquantum) electronic elements with memory. The equilibrium points of the circuit represent the approximation to the problem at hand. Then, we solve its associated nonlinear ordinary differential equations numerically, towards the equilibrium points. We demonstrate this exponential gain by comparing a sequential MATLAB implementation of our solver with the winners of the 2016 Max-SAT competition on a variety of hard optimization instances. We show empirical evidence that our solver scales linearly with the size of the problem, both in time and memory, and argue that this property derives from the collective behavior of the simulated physical circuit. Our approach can be applied to other types of optimization problems, and the results presented here have far-reaching consequences in many fields.


---

## Body

## 1. Introduction

In real-life applications, it is common to encounter problems where one needs to find the best solution within a vast set of possible solutions. Theseoptimization problems are routinely faced in many commercial segments, including transportation, goods delivery, software packages or hardware upgrades, network traffic and congestion management, and circuit design, to name just a few [1, 2]. Many of these problems can be easily mapped into combinatorial optimization problems, namely, they can be written as Boolean formulas with many constraints (clauses) among different variables (either negated or not, i.e., literals) with the constraints themselves related by some logical proposition [1].It is typical to write the Boolean formulas asconjunctions (the logical ANDs, also represented by the symbol ∧) of disjunctions (the logical ORs, represented by the symbol ∨), in the so called conjunctive normal form (CNF). The CNF representation is universal in that any Boolean formula can be written in this form [3].A simple example of a CNF formulaϕx is
(1)ϕx=¬x1∨x2∧¬x2∨¬x3∨x4∧x1∨¬x2∨x3∨¬x4∧¬x1∨x4∧x1∨x2∨¬x4,in which we have four variables, xj, with j=1,2,3,4, five clauses, and fourteen literals (the symbol ¬ indicates negation). The problem is then to find an assignment satisfying the maximum number of clauses, that is, in which as many clauses as possible have at least one literal that is true. Such a clause is then said to be satisfied, otherwise it is unsatisfied [3], and the problem itself is known as Max-SAT (maximum satisfiability).A Max-SAT problem whose CNF representation has exactlyk literals k≥2 per clause is called Max-EkSAT. Max-EkSAT is a ubiquitous optimization problem with widespread industrial applications. We will focus on its solution as a test bed in the main text and refer the reader to the appendix where we have applied our approach to a wide range of optimization problems, including weighted Max-SAT, [4] for its application to machine learning and [5] for the solution of the worst cases of a satisfiable problem known as the subset sum.Max-EkSAT lies in the NP-hard class, meaning that any problem in NP can be reduced to it in polynomial time [1]. More informally, we expect that worst case instances will require resources which grow (at least) exponentially in the input size to solve, and additionally, problems in this class generally also require exponential resources in order to check a proposed solution. Due to this, complete algorithms that attempt to solve Max-EkSAT instances quickly become infeasible for large problems. Much research has instead focused on incomplete solvers that perform a stochastic local search, by generating an initial assignment and iteratively improving upon it. This approach has proven effective at approximating and sometimes solving large instances of SAT and other problems. For instance, in recent Max-SAT competitions [6], incomplete solvers outpace complete solvers by two orders of magnitude on random and crafted benchmarks. However, they too suffer from the same exponential time dependence as complete solvers for sufficiently large or hard instances [7–9].It has further been shown, using probabilistically checkable proofs [10], that many classes of combinatorial optimization problems (including the Max-EkSAT) have an inapproximability gap. This means that no algorithm can overcome, in polynomial time, a fraction of the optimal solution, unless NP = P [10, 11]. In other words, for heuristics to improve on their approximation beyond this limit would require exponentially increasing time. For example, for the Max-E3SAT, it has been proved that if NP≠P, then there is no algorithm that can give an approximation better than 7/8 of the optimal number of satisfied clauses [11].Despite these difficulties, it is often necessary to solve or approximate optimization problems such as these as quickly as possible, and the quality of the approximation can have direct outcomes on the cost to businesses, the speed of our internet connections, or the efficiency of our shipping, to name a few important cases. In what follows, we outline a novel approach to generating approximations to Max-EkSAT and demonstrate its efficacy on a variety of instances both generated to provide the worst cases within the inapproximability gap and drawn from Max-SAT competitions [6].


## 2. The Memcomputing Approach

In this work, we consider a radically differentnoncombinatorial approach to hard optimization problems. Our approach is based on the simulation of digital memcomputing machines (DMMs) [5, 12, 13]. A brief introduction of these machines is provided in the appendix. The reader interested in a more in-depth discussion is urged to look at the extensive papers [5, 12]. The practical realization of DMMs can be accomplished using standard circuit elements and those with memory (time nonlocality, hence the name “memcomputing” [14]).Time nonlocality allows us to build logic gates thatself-organize into their logical proposition, irrespective of whether the signal comes from the traditional input or output [12]. We call them self-organizing logic gates (SOLGs), and circuits built out of them, self-organizing logic circuits (SOLCs). Our approach then follows these steps.
(1)
We first construct the Boolean circuit that represents the problem at hand (e.g., the Max-EkSAT of Figure 1).
(2)
We replace the traditional (unidirectional) Boolean gates of this Boolean circuit with SOLGs.
(3)
We feed the appropriate terminals with the required output of the problem (e.g., the logical 1 if we are interested in checking its satisfiability).
(4)
Finally, the electronic circuit built out of these SOLGs can be described bynonlinear ordinary differential equations, which can be solved to find the equilibrium (steady-state) points. These equilibria represent the approximation to the optimization problem [12].Figure 1
Example of the mapping between a Boolean satisfiability formula in conjunctive normal form and a Boolean circuit made of multiterminal OR and NOT gates. Each clause of the SAT formula is mapped into an OR with as many terminals as the literals in the clause (the satisfiability of this multiterminal OR requires that at least one terminal has a truth value of 1). The global optimum of the SAT formula, that is, the maximum number of satisfied clauses, corresponds to the maximum number of OR gates with output one. This Boolean circuit is then transformed into a self-organizing logic circuit by substituting each standard Boolean gate with a self-organizing logic gate [12], and each OR output is fed with a DC voltage generator representing the logic value of 1.The procedure of how we transform a combinatorial optimization problem into an electronic circuit as well as a sketch of its numerical solution is discussed further in the appendix (see also [12]). The important point to note is that SOLGs and SOLCs manifest long-range order due to the presence of instantons [15]. Instantons connect topologically inequivalent critical points in the phase space, hence generating nonlocality in the system. This translates into a collective dynamical behavior that allows gates at an arbitrary distance to correlate very efficiently so that, when a terminal of one gate needs to change its truth value to satisfy that gate’s logical proposition, a terminal at any other gate may provide the correct truth assignment while satisfying its own logical proposition [5]. As we will explain later, this is the key feature that allows these memcomputing machines to solve complex problems efficiently, without the need to explore a vast space of possibilities, as standard combinatorial approaches would do.


## 3. Results and Discussion

This radical change of perspective manifests its power already in comparing simulations of DMMs with those performed by the winners of the 2016 Max-SAT competition [6] on the competition benchmarks. When run on similar hardware, our solver, which we named Falcon [12, 16, 17], performs orders of magnitude faster than the winners in the incomplete track of the competition, and in some cases it finds the solution when the best solvers did not.Since a direct comparison is difficult across hardware and implementations (our solver is written in MATLAB which is notoriously inefficient compared with the compiled languages of the competition solvers). Nevertheless, these tests already provide strong indication of the advantages of our approach using digital memcomputing machines over traditional combinatorial optimization.However, in order to form a direct comparison and more clearly show theexponential speed-up of our approach, we have crafted three Max-SAT problems with increasing levels of difficulty. We then compared our memcomputing solver against two of the best solvers of the 2016 Max-SAT competition (CCLS [18] and DeciLS [19]—a new version of CnC-LS—kindly provided by their developers) which are specifically designed to solve these types of problems, but employing very different solution strategies.Random 3-SAT instances may be generated by selecting 3 variables out ofn, joining them in a 3-SAT clause where each is randomly negated and then repeating this for the desired number of clauses M. These instances are known to undergo a SAT/UNSAT transition when the ratio of clauses to variables, M/n=ρ (hereafter the “density”), crosses the critical value ρc≈4.3 [20, 21]. Exponential time is required to demonstrate that an instance is UNSAT [22] and thus must also be required to solve the corresponding Max-SAT, offering a simple way to generate benchmarks.However, the difficulty of computing approximations for these instances varies widely. This can be partially attributed to the fluctuations in variable occurrences and their negations [23] leading to “fields” which point towards the optima. More balanced instances may be produced by starting with a Random-XORSAT instance (also called hyperSAT [24]), that is, a set of Boolean formulas defined by the XOR of Boolean variables (the XOR symbol is ⊕) and converting it to a Max-SAT instance.Each XORSAT clause may be converted to a block of four SAT clauses, for example,(2)x⊕y⊕z=1→x∨y∨z∧x∨¬y∨¬z∧¬x∨¬y∨z∧¬x∨y∨¬z,in which a variable and its negation appear symmetrically. The special structure of XORSAT gives rise to a global algorithm when the instance is satisfiable, allowing for a solution in polynomial time using Gaussian elimination [24]. However, when unsatisfiable, occurring for ρ>4⋅0.918≈3.7, this same structure makes these problems very difficult for local search solvers [22, 25]. In addition, the choice of instances out of XORSAT clauses makes them particularly difficult also for algorithms based on message passing [26].A basic understanding of this difficulty can be obtained by considering that changing a variable assignment affects positively (namely, contributes a true literal to) the same number of clauses as those affected negatively (where the literal is false), because of the balanced occurences of the variables. Therefore, for any combinatorial approach, when a certain amount of satisfied clauses is reached, any further improvement requires manysimultaneous variable flips, which is a nonlocal type of assignment. In other words, the distance between two assignments at successive approximations becomes of the same order of the input length ∣x∣. This means that going from an assignment x to a better one y, if they have a distance dx,y=∑jxj−yj2=Ox, would require checking O2dx,y variable flips, which is the number of configurations that is exponential with respect to the distance dx,y (the actual calculation requires the enumeration of all possible flips of 1,2,…,dx,y literals because the distance dx,y is not known a priori. Hence, the actual number of flips is ∑k=0dx,yk∣x∣≥2dx,y).While more difficult, these instances also display some variation in resolution time. In order to obtain instances of more predictable difficulty, we impose a further constraint requiring all variables to appear the same number of times (or as near as possible while remaining consistent with the number of clausesM=ρN), that is, the variable occurrences are distributed as a δ-function. This variant is harder than the previous one because of the additional balance induced by the variable distribution, and our results indicate that they display much lower variability in their difficulty.In the following, we will call “random-Max-E3SAT” a Max-E3SAT completely generated at random. This will be used as an “easy” problem to test the performance of all solvers. We refer to “hyper-Max-E3SAT” as the Max-E3SAT generated from a random Max-E3XOR and finally to “delta-Max-E3SAT” as a problem generated by the Max-E3XOR withδ-function distribution of variables.As it is evident in Figure2, while the balanced structure of Max-XORSAT poses a challenge to local search algorithms, our memcomputing solver easily overcomes these limits because, due to the collective (instantonic) behavior of the circuit, the dynamics evolve towards deep minima very close to the global optimum (see also the appendix). The reason is that, as already anticipated, the collective state of the machine allows simultaneous, nonlocal change of literals belonging to gates arbitrarily far from each other [15]. This change is consistent with the physics and the topology of the memcomputing circuit that naturally drive the system towards the maximum number of satisfied SOLGs, without recourse to any combinatorial selection scheme.Figure 2
Simulation time comparison between incomplete solvers CCLS and DeciLS against our solver, Falcon, for the balanced and constrained delta-Max-E3SAT. A threshold of1.5% of unsatisfiable clauses has been set. We have then tested how long CCLS, DeciLS, and our solver Falcon take to overcome this limit with increasing number of variables. All calculations have been performed on a single thread of an Intel Xeon E5-2680 v3 with 128 Gb DRAM shared on 24 threads. The local solvers require an exponentially increasing time to reach that limit already visible at a few hundred variables for the CCLS and a few thousands for the DeciLS. Our solver has been tested up to 2×106 variables and required order of 104 seconds for that maximum number of variables. We show also the estimate of time that would have been required these local solvers to run up to 2×106 variables. The estimated time (dashed and dashed-dotted lines) has been calculated using a linear regression of the log10time versus the number of variables.The optimum for all problems can be estimated using an ensemble of small instances for which it is easier to find a fairly good approximation. For example, instances of about 300 variables and density (clauses/variables) ofρ=5 provide a good indication of the global optimum in terms of percentage of unsatisfied clauses. We found that for the random-Max-E3SAT, the optimum is expected at about 0.4% of unsatisfied clauses, while for both the hyper- and delta-Max-E3SAT, this value is about 1.3%. The difference between these values is not surprising. As mentioned previously, it is well known that for the latter two problems the transition from satisfiable to unsatisfiable is around a density of ρ≈3.7, while for random-Max-E3SAT, it is around ρ≈4.3. We have then chosen the same density of ρ=5 for the random-, hyper-, and delta-Max-E3SAT.In order to prove the superior efficiency of our noncombinatorial approach for this class of hard problems, we have evaluated their scaling properties up to2×106 variables (while keeping the density constant). We recall that the simulations of DMMs have been done using a MATLAB code, while CCLS and DeciLS are compiled codes. Therefore, the level of optimization is expected to be higher in the compiled codes, making a direct performance comparison harder, although for large problem sizes, our solver has much better performance compared to CCLS and DeciLS. Nevertheless, we are more interested in the scaling of the approximation time. Specifically, for hard cases where incomplete solvers diverge exponentially in time, our solver diverges linearly. This is the most important test and the central result of our paper. It is shown in Figure 2.The hard inapproximability limit and its exponential nature for both the combinatorial heuristics CCLS and DeciLS is clearly visible in Figure2, where we have set a threshold of 1.5% of unsatisfiable clauses for the delta-Max-E3SAT. We have then tested how long CCLS, DeciLS, and our solver Falcon take to overcome this limit with increasing number of clauses. All calculations have been done on a single core of an Intel Xeon E5-2680 v3.The exponential blowup of CCLS and DeciLS is already evident for small instances of the problem, while our noncombinatorial approach performslinearly, in both time and memory, for any number of variables we have tested so far. In fact, we have tested our solver up to 2×106 variables, requiring ∼104 seconds to reach the target 1.5% threshold. The heuristic solvers, if they could run up to the same number of variables, would require, in the best case, about ∼102500 seconds, which is ∼102480 times the estimated age of the universe.To better highlight thelinear scaling of our solver, we compare it in Figure 3 with CCLS (qualitatively, all other incomplete solvers should perform similarly). Each plot of Figure 3 displays the percentage of unsatisfied clauses versus time, normalized with respect to the number of variables n. Clearly, linear scaling for these hard problems is a very desirable feature and very difficult to achieve with combinatorial approaches. However, the reason for such linear scaling is subtle.Figure 3
Comparison between the incomplete solver CCLS versus our noncombinatorial solver, Falcon, for (a) random-Max-E3SAT, (b) hyper-Max-E3SAT, and (c) delta-Max-E3SAT. In these plots, the percentage of unsatisfied clauses versus the time normalized with respect to the number of variables is shown to highlight the linear scaling of our solver. All calculations have been performed on a single thread of an Intel Xeon E5-2680 v3 with 128 Gb DRAM shared on 24 threads.
(a)
(b)
(c)Regardingmemory, since we simulate (integrate) differential equations in time, and the circuit scales linearly with the number of literals, the linear scaling in memory requirements of our simulations is easy to understand (see also the appendix). On the other hand, linear scaling in simulation time implies constant scaling, namely, independent of the problem size, when we look at the “machine time,” which is the number of (differential equation discretized time) steps for the simulation to reach equilibrium. The reason for this unexpected machine time constant scaling can be found again in the long-range order of the dynamics of the system [15] (see also the appendix). As we have shown analytically in [15] using topological field theory, this long-range order leads to nondecreasing spatial (and temporal) correlations in memcomputing machines. In fact, Figure 3 clearly shows that self-organizing logic circuits relax close to the predicted global minimum, while the CCLS does so only for the (“easy”) random-Max-E3SAT. This is further illustrated in Figure 4 of the appendix for random-, hyper-, and delta-Max-E3SAT.Figure 4
Comparison between the CCLS solver versus our solver, Falcon, for (a) random-Max-E3SAT, (b) hyper-Max-E3SAT, and (c) delta-Max-E3SAT. In these plots, the percentage of unsatisfied clauses versus the number of variables is shown. Different curves are for different simulation time-outs (in seconds) following the relationtout=kn with n=∣x∣ and k an integer given in the legend. All calculations have been performed on a single thread of an Intel Xeon E5-2680 v3 with 128 Gb DRAM shared on 24 threads.
(a)
(b)
(c)


## 4. Conclusions

In conclusion, we have shown empirical evidence that anoncombinatorial approach—based on the simulation of digital memcomputing machines—to the solution of hard combinatorial optimization problems outperforms exponentially heuristics specifically designed to solve such problems. In particular, with our approach, we were able to find far better approximations to hard instances with millions of variables in a few hours on a single core, with linear scaling both in time and memory of the processor. For the same sizes, winners of the 2016 Max-SAT competition would require several orders of magnitude more than the age of the universe to find the same approximations. Of course, these numerical results are not intended to prove that there are polynomial solutions to NP-hard problems. Rather, they show that physics-inspired approaches can help tremendously in solving some of the most complex problems faced in academia and industry. We thus hope that this work will motivate further research along these lines.



---

*Source: 7982851-2018-07-03.xml*