Unweighted Stochastic Local Search can be Effective for Random CSP Benchmarks

We present ULSA, a novel stochastic local search algorithm for random binary constraint satisfaction problems (CSP). ULSA is many times faster than the prior state of the art on a widely-studied suite of random CSP benchmarks. Unlike the best previous methods for these benchmarks, ULSA is a simple unweighted method that does not require dynamic adaptation of weights or penalties. ULSA obtains new record best solutions satisfying 99 of 100 variables in the challenging frb100-40 benchmark instance. 1 Random Binary CSPs Randomly generated instances of constraint satisfaction problems (CSP) have provided widely-used benchmarks in the development of solvers for CSP, Boolean satisfiability (SAT), and maximum independent set (MIS). While some interesting instances of CSP and SAT eventually turn out to be reasonably easy for appropriate methods (Minton, Johnston, Philips, & Laird, 1990; Williams, Gomes, & Selman, 2003), reliably hard instances of random CSP can be obtained from the “phase transition” boundary between satisfiable and unsatisfiable regions of parameterized distributions of instances (Prosser, 1996). For appropriate distributions, most of these phase transition instances are exponentially hard for a standard baseline approach of tree-like resolution (Xu & Li, 2006). And empirically these phase transition instances are challenging for all known methods. A discrete constraint satisfaction problem (CSP) consists of n variables x1 . . . xn. Each variable xi can be assigned a value from its finite domain Di. In this paper, all variables in an instance have the same domain size. An instance specifies a set of constraints, where each constraint identifies k variables and restricts them to an allowed subset of combinations of values from the cross product of their domains. Here, we deal with binary CSPs in which k = 2, and we refer to the two variables in a constraint as endpoints of the constraint. If two endpoints hold values that violate the constraint, we refer to it as a conflict. A solution to the CSP is a setting to the variables in which there are no conflicts. We also refer to partial solutions as meeting a target of T ≤ n if there is a subset of T variables such that no conflict has both endpoints in this subset. Several models have been developed for generating hard random CSP instances (Smith & Dyer, 1996). Model RB addresses shortcomings of early models (Xu & Li, 2000), and has received wide attention. To generate a random binary CSP with n variables, Model RB draws (with replacement) rn ln(n) variable pairs to constrain. For each of these variable pairs, the constraint disallows 1 ar X iv :1 41 1. 74 80 v1 [ cs .A I] 2 7 N ov 2 01 4 a fraction p of pairs of values; the specific pairs are drawn randomly (without replacement), independently for each constraint. With n variables, a phase transition occurs (asymptotically) when domain size is n0.8, r = 0.8/(ln(4) − ln(3)), and p = 0.25 (Xu & Li, 2003). It is also possible to modify Model RB slightly to generate forced-satisfiable instances that are guaranteed to have a solution, by rejecting any constraints that are inconsistent with a preselected solution; such forced-satisfiable instances have very similar properties to the original Model RB (Xu, Boussemart, Hemery, & Lecoutre, 2007). A particular benchmark suite of forced-satisfiable Model RB instances (Xu, 2003, 2005), denoted frbX-Y for X variables and domain size Y, has been used repeatedly in CSP solving competitions (Boussemart, Hemery, & Lecoutre, 2005; van Dongen, Lecoutre, & Roussel, 2006, 2008, 2009), SAT solving competitions (van Maaren & Franco, 2014), and many published CSP and SAT studies (Mehta & van Dongen, 2005; Xu et al., 2007; Cai, Su, & Sattar, 2011). These benchmarks have been very challenging in CSP and SAT competitions; for example, instance frb59-26-2 appeared in at least 6 competitions from 2004-2011 without ever being solved by any of the competitors. This benchmark suite has had particular importance in the development of MIS solvers (Cai, Su, & Chen, 2010; Pullan, Mascia, & Brunato, 2011; Cai, Su, Luo, & Sattar, 2013).1 Given an undirected graph, the MIS problem asks for the largest subset of vertices such that no edge has both endpoints in the subset. For MIS, the graph formulation of this benchmark suite (known as BHOSLIB) relies on a straightforward reduction from binary CSP to MIS: given a CSP instance, the corresponding MIS instance has a vertex for each possible domain value of each variable, an edge for each pair of values disallowed by a constraint, and an edge for each pair of values for the same variable since a variable can only hold one value.2 Independent sets of size n correspond to solutions to the original n-variable CSP instance, and independent sets of size T ≤ n correspond to partial CSP solutions meeting a target of T . As MIS solvers have become more capable via improved algorithms and increased computer speed, most of the MIS benchmarks in the older DIMACS suite are readily solved, making BHOSLIB an important source of newer challenging MIS benchmarks (Richter, Helmert, & Gretton, 2007; Pullan et al., 2011; Cai et al., 2013). The importance of BHOSLIB extends to use in the development of MIS solvers for practical biomedical applications (Bull, Muldoon, & Doig, 2013; Abraham & Diaz, 2014). Substantially improved MIS results on DIMACS and BHOSLIB instances have come through use of stochastic local search algorithms that dynamically adapt weights or penalties on vertices (Pullan & Hoos, 2006; Pullan et al., 2011), edges (Cai et al., 2010, 2013), or both (Fang, Chu, Qiao, Feng, & Xu, 2014). MIS solvers using such weighted search techniques have yielded the best results for the BHOSLIB benchmarks. Instead of “maximum independent set” or ”MIS”, some studies refer to the equivalent problems of “minimum vertex cover” or “maximum clique.” We confirmed (by inspection of subset of the BHOSLIB MIS instances that had previously been made available in CSP form) that the BHOSLIB MIS instance vertices are numbered sequentially starting with all of the domain values for one CSP variable, then all of the domain values for a second CSP variable, and so on. This made it straightforward to recover the binary CSP instances from their MIS versions. Had this straightforward recovery not been possible (e.g. due to random permutation of vertices in the MIS instance), we also confirmed that it is feasible to recover the CSP variables from the MIS instance with brief runs of a max clique heuristic (NuMVC operating on the inverse of the graph) to identify the large cliques in the MIS instance that represent the domain values of the CSP variables.