Structure in combinatorial optimization and its effect on heuristic performance

Abstract

The goal in combinatorial optimization is to find a good solution among a finite set of solutions. In many combinatorial problems, the set of solutions scales at an exponential or greater rate with the instance size. The maximum boolean satisfiability (MAX-SAT) is one such problem that has many important theoretical and practical applications. Due to the exponential growth of the search space, sufficiently large instances of MAX-SAT are intractable for complete solvers. Incomplete solvers, such as stochastic local search (SLS) algorithms are necessary to find solutions in these cases. Many SLS algorithms for MAX-SAT have been developed on randomly generated benchmarks using a uniform distribution. As a result, SLS algorithms for MAX-SAT perform exceptionally well on uniform random instances. However, instances from real-world applications of MAX-SAT have a structure that is not captured in expectation by uniform random problems. The same SLS algorithms that perform well on uniform instances have a drastic drop in performance on structured instances. To better understand the performance drop on structured instances, we examine three characteristics commonly found in real-world applications of MAX-SAT: a power-law distribution of variables, clause lengths following a power-law distribution, and a community structure similar to that found in small-world models. We find that those instances with a community structure and clause lengths following a power-law distribution have a significantly more rugged search space and larger backbones than uniform random instances. These search space properties make it more difficult for SLS algorithms to find good solutions and in part explains the performance drop on industrial instances. In light of these findings, we examine two ways of improving the performance of SLS algorithms on industrial instances. First, we present a method of tractably computing the average evaluation of solutions in a subspace that we call a hyperplane. These averages can be used to estimate the correct setting of the backbone variables, with as high as 90% accuracy on industrial-like instances. By initializing SLS algorithms with these solutions, the search is able to find significantly better solutions than using standard initialization methods. Second, we re-examine the trade-offs between first and best improving search. We find that in many cases, the evaluation of solutions found by SLS algorithms using first improving search are no worse, and sometimes better, than those found by best improving. First improving search is significantly faster; using first improving search with AdaptG2WSAT, a state-of-the-art SLS algorithm for MAX-SAT, gives us more than a 1,000x speedup on large industrial instances. Finally, we use our hyperplane averages to improve the performance of complete solvers of the satisfiability problem (SAT), the decision version of MAX-SAT. We use the averages to heuristically select a promising hyperplane and perform a reduction of the original problem based on the chosen hyperplane. This significantly reduces the size of the space that must be searched by the complete solver. Using hyperplane reduction as a preprocessing step, a standard complete SAT solver is able to outperform many state-of-the-art complete solvers. Our contributions have advanced the understanding of structured instances and the performance of both SLS algorithms and complete solvers on these instances. We also hope that this work will serve as a foundation for developing better heuristics and complete solvers for real-world applications of SAT and MAX-SAT.