One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction

1 Introduction

Constraint Satisfaction Problems (CSP) are a ubiquitous framework for specifying combinatorial search and optimization problems. They include many of the best-known NP-hard problems such as Boolean satisfiability (SAT), graph coloring (COL) and maximum cut (MAXCUT) and can flexibly adapted to model specific application dependent problems. CSP solution strategies range from general solvers based on methods such as constraint propagation or local search (see [Russell et al., 2020], Chapter 6) to specialized solvers for individual problems like SAT (see [Biere et al., 2021]). In recent years, there is a growing interest in applying deep learning methods to combinatorial problems including many CSPs (e.g. [Khalil et al., 2017], [Selsam et al., 2018], [Tönshoff et al., 2021]). The main motivation for these approaches is to learn novel heuristics from data rather than crafting them by hand.

∗This work was supported by the German Research Foundation (DFG) under grants GR 1492/16-1 and KI 2348/1-1 "Quantitative Reasoning About Database Queries".

Graph Neural Networks (see Gilmer et al. 2017) have emerged as an effective tool for learning powerful, permutation invariant functions on graphs using deep neural networks, and they have become the primary architecture for neural combinatorial optimization. Problem instances are modelled as graphs and then mapped to approximate solutions with GNNs. However, most methods use graph reductions and GNN architectures that are problem specific. Transferring them across combinatoral tasks requires considerable engineering, limiting their use cases. Designing a generic neural network architecture and training procedure for the general CSP formalism offers a powerful alternative. Then learning heuristics for any specific CSP becomes a purely data driven process requiring no specialized graph reduction or architecture search.

We propose a novel GNN based reinforcement learning approach to general constraint satisfaction. The main contributions of our method called ANYCSP 1 can be summarized as follows: We define a new graph representation for general CSP instances which is generic and well suited as an input for recurrent GNNs. It allows us to directly process all CSPs with one unified architecture and no prior reduction to more specific CSPs, such as SAT. In particular, one ANYCSP model can take every CSP instance as input, even those with domain sizes, constraint arities, or relations not seen during training. Training is unsupervised using policy gradient ascent with a carefully tailored reward scheme that encourages exploration and prevents the search to get stuck in local maxima. During inference, a trained ANYCSP model iteratively searches the space of assignments to the variables of the CSP instance for an optimal solution satisfying the maximum number of constraints. Crucially, the search is global; it allows transitions between any two assignments in a single step. To enable this global search we use policy gradient methods to handle the exponential action spaces efficiently. This design choice speeds up the search substantially, especially on large instances. We thereby overcome a primary bottleneck of previous neural approaches based on local search, which only flip the values of a single or a few variables in each step. GNN based local search tends to scale poorly to large instances as one GNN forward pass takes significantly more time than one step of classical local search heuristics. ANYCSP addresses this by exploiting the GNNs inherent parallelism to refine solutions globally.

1 Are Neural Networks great heuristics? Yes, for CSPs.

We evaluate ANYCSP by learning heuristics for a range of important CSPs: COL, SAT, MAXCUT and general CSP benchmark instances. We demonstrate that our method achieves a substantial increase in performance over prior GNN approaches and can compete with conventional algorithms. ANYCSP models trained on small random graph coloring problems are on par with state-of-the-art coloring heuristics on structured benchmark instances. On MAX-k-SAT, our method scales to test instances 100 times larger than the training data, where it outperforms state-of-the-art search heuristics despite performing 1000 times fewer search iterations.

2 RelatedWork

In this paper, we are primarily interested in end-2-end approaches which directly predict approximate solutions for combinatorial problems with neural networks. Another line of work integrates deep learning components into more traditional solvers (i.e. [Gasse et al., 2019; Zhang et al., 2020]). While also quite interesting, these are at most loosely related to our work, and we leave them out of the following discussion. For a comprehensive overview on neural combinatorial optimisation, we refer to [Cappart et al., 2021].

Early work was done by [Bello et al., 2016], who learned TSP heuristics with Pointer Networks [Vinyals et al., 2015] and policy gradient descent. Several extensions of these ideas have since been proposed based on attention [Kool et al., 2018] and GNNs [Joshi et al., 2020]. [Khalil et al., 2017] propose a general method for graph problems, such as MAXCUT or Minimum Vertex Cover. They model the expansion of partial solutions as a reinforcement learning task and train a GNN with Q-learning to iteratively construct approximate solutions.

A related group of approaches models local modifications to complete solutions as actions of a reinforcement learning problem. A GNN is then trained as a local search heuristic that iteratively improves candidate solutions through local changes. Methods following this concept are RLSAT [Yolcu and Póczos, 2019] for SAT, ECO-DQN [Barrett et al., 2020] for MAXCUT, LS-DQN [Yao et al., 2021] for graph partitioning problems and TSP as well as BiHyb [Wang et al., 2021] for graph problems based on selecting and modifying edges. Like conventional search heuristics, these architectures can be applied for any number of search iterations to refine the solution. A shared drawback on large instances is the relatively high computational cost of GNNs, which slows down the search substantially when compared to classical algorithms. ECORD [Barrett et al., 2022] addresses this issue for MAXCUT by applying a GNN once before the local search, which is carried out by a faster GRU-based architecture without message passes. We address the same problem, but not by iterating faster, but by allowing global modifications in each iteration.

A fundamentally different approach considers soft relaxations of the underlying problems which can optimized directly with SGD. Examples of this concept are PDP [Amizadeh et al., 2019] for SAT and RUNCSP [Tönshoff et al., 2021] for all binary CSPs with fixed constraint language. These architectures can predict completely new solutions in each iteration but the relaxed differentiable objectives used for training typically do not capture the full hardness of the discrete problem.

3 Preliminaries

A CSP instance is a triple I = (X,D,C), where X is a finite set of variables, D assigns to each variable X ∈ X a finite set D(X), the domain of X, and C is a set of constraints C = (sC ,RC ), where for some k ≥ 1, the scope sC = (X1, . . . ,Xk) ∈ Xk is a tuple of variables and RC ⊆ D(X1) × . . . ×D(Xk) is a k-ary relation over the corresponding domains. We always assume that the variables in the scope sC of a constraint C are mutually distinct; we can easily transform an instance not satisfying this condition into one that does by adapting the relation RC accordingly.

Slightly abusing terminology, we call a pair (X, d) where X ∈ X and d ∈ D(X) a value for variable X. For all X ∈ X we let VX = {X} ×D(X) be the set of all values for X, and we let V = ⋃X∈X VX be the set of all values. We usually denote values by v. Working with these values instead of domain elements is convenient because the sets VX, for X ∈ X, are mutually disjoint, whereas the domains D(X) are not necessarily.

An assignment for a CSP instance I = (X,D,C) is a mapping α that assigns a domain element α(X) ∈ D(X) to each variable X. Alternatively, we may view an assignment as a subset α ⊆ V that contains exactly one value from each VX. Depending on the context, we use either view, and we synonymously write α(X) = d or (X, d) ∈ α. An assignment α satisfies a constraint C = ((X1, . . . ,Xk),R) (we write α |= C) if (α(X1), . . . , α(Xk)) ∈ R, and α satisfies I, or is a solution to I, if it satisfies all constraints in C. The objective of a CSP is to decide if a given instance has a satisfying assignment and to find one if it does. To distinguish this problem from the maximization version introduced below, we sometimes speak of the decision version. Specific CSPs such as Boolean satisfiability or graph coloring problems are obtained by restricting the instances considered.

We define the quality QI(α) of an assignment α to be the fraction of constraints in C satisfied by α: QI(α) = |{C|C ∈ C, α |= C}|/|C|. An assignment α is optimal if it maximizes QI(α) for the instance I. The goal of the maximisation problem MAXCSP is to find an optimal assignment for a given instance. A soft assignment for a CSP instance I is a mapping φ : V → [0, 1] such that ∑v∈VX φ(v) = 1 for all X ∈ X. We interpret the numbers φ(v) as probabilities and say that an assignment α is sampled from a soft assignment φ (we write α ∼ φ) if for each variable X ∈ X we independently draw a value v ∈ VX with probability φ(v).

4 Method

With every CSP instance I = (X,D,C) we associate a tripartite graph with vertex set X ∪ V ∪ C, where V is the set of values defined in the previous section, and two kinds of edges: variable edges (X, v) for all X ∈ X and v ∈ VX, and constraint edges (C, v) for all C ∈ C and v ∈ VX for some X in the scope of C. This graph representation is more or less standard; one slightly unusual feature is that we introduce edges from constraints directly to the values and not to the variables. This will be important in the next step, where information about the constraint relations RC is compactly encoded through a binary labeling of the constraint edges. For each assignment α we introduce a vertex labeling LV and an edge labeling LE. The vertex labeling LV is a binary encoding of α, that is, LV (v) = 1 if v ∈ α and LV (v) = 0 for each v ∈ V \ α. The edge labeling LE encodes how changes to α affect each constraint. For every constraint C ∈ C and value (Xi, d) ∈ VXi of variable Xi in the scope (X1, . . . ,Xk) of C we define the edge label to be LE(C, v) = 1 if

and LE(C, v) = 0 otherwise. Intuitively, the edge labels encode for each constraint edge (C, v) whether or not choosing the value v for its variable would satisfy C under the condition that all other variables involved in C retain their current value in α. We call the labeled graph G(I, α) obtained this way the constraint value graph of I at α. Figure 1 provides a visual example of our construction.

A complete encoding of each constraint relation would have exponential worst-case space requirements. Our method avoids this issue through a partial encoding using edge labels that dynamically adapts to the current assignment. In Appendix 2 A.5 we provide details on efficiently recomputing the edge labels for a new assignment α and a discussion on global constraints.

4.1 Architecture

We construct a recurrent GNN πθ that maps constraint value graphs to soft assignments and serves as a trainable policy for our reinforcement-learning setup. Here, the real vector θ contains the trainable parameters of πθ. The input of πθ in iteration t is the current graph G(I, α(t-1) ) and recurrent vertex states h(t-1) . The output is a new soft assignment φ(t) for I as well as updated recurrent states:

The next assignment α(t) can then be sampled from φ(t) before the process is repeated. Here, we will provide an overview of the GNN architecture while we give a detailed formal description in Appendix A.

In a nutshell, our architecture is a recurrent heterogeneous GNN that uses distinct trainable functions for each of the three vertex types in the constraint value graph. The main hyperparameters of πθ are the latent dimension d ∈ N and the aggregation function ⊕ which we either choose as an elementwise SUM, MEAN or MAX function. We usually found MAX to perform best on decision problems while MEAN worked better for maximization tasks. This coincides with observations of [Joshi et al., 2020].

πθ associates a recurrent state h(t) (v) ∈ Rd with each value v ∈ V and uses a GRU cell to update these states after each round of message passing. Variables and constraints do not have recurrent states. We did consider versions with stateful constraints and variables, but these did not perform better while being slower. All remaining functions for message generation and combination are parameterized by standard MLPs with at most one hidden layer. In each iteration t, πθ performs 4 directed message passes in the following order: (1) values to constraints, (2) constraints to values, (3) values to variables, (4) variables to values. The first two message passes incorporate the node and edge labels and enable the values to gather information about how changes to the current assignment effect each constraint. The final two message passes allow the values of each domain to negotiate the next variable assignment. Note that this procedure is carried out once in each search iteration t. As the recurrent states can carry aggregated information across search iterations we found a single round of message passes per iteration sufficient.

Finally, πθ generates a new soft assignment φ(t) . To this end, each value v ∈ VX of each variable X predicts a scalar real number o(t) (v) = O(h(t) (v)) from its updated latent state with a shared MLP O : Rd → R. We can then apply the softmax function within each domain to produce a soft value assignment:

2 Code and Appendix: https://github.com/toenshoff/ANYCSP

This procedure leverages a major strength of our graph construction: By modeling values as vertices we can directly process arbitrary domains with one GNN. For larger domains, we simply add more value vertices to the graph.

4.2 Global Search as an RL Problem

We deploy the policy GNN πθ as a trainable search heuristic. Note that a single GNN πθ can search for solutions on any given CSP instance. ANYCSP takes a CSP instance I and a parameter T ∈ N as input and outputs a sequence α = α(0) , . . . , α(T) of assignments for I. The initial assignment α(0) is simply drawn uniformly at random. In each iteration 1 ≤ t ≤ T the policy GNN πθ is applied to the current constraint value graph G(I, α(t-1) ) to generate a new soft assignment φ(t) . The next assignment α(t) ∼ φ(t) is then sampled from the predicted soft assignment by drawing a new value α(t) (X) for all variables X independently and in parallel without imposing any restrictions on locality. Any number of variables may change their value in each iteration which makes our method a global search heuristic. This allows ANYCSP to modify different parts of the solution simultaneously to speed up the search. Figure 2 provides a visual illustration of the overall process. Formally, our action space is the set of all assignments for the input instance, one of which must be chosen as the next assignment in each iteration t. This set is extremely large for many CSPs, with up to 1050 assignments to choose from for some of our training instances. Despite this, we found standard policy gradient descent algorithms to be effective and stable during training.

Rewarding Iterative Improvements. We devise a reward scheme that assigns a real-valued reward r(t) to each generated assignment α(t) . A simple approach would be to use the quality QI(α(t) ) as a reward. However, we found that models trained with this reward tend to get stuck in local maxima and have comparatively poor performance. Intuitively, this simple reward scheme immediately punishes the policy for stepping out of a local maximum causing stagnating behavior.

We, therefore, choose a more sophisticated reward system that avoids this issue. First, we define the auxiliary variable q(t) = maxt′<t QI(α(t′ ) ), which tracks the highest quality achieved before iteration t. We then define the reward in iteration t as follows:

The policy earns a positive reward in iteration t if the new assignment α(t) satisfies more constraints than any assignment generated in the previous steps. In this case, the reward is the margin of improvement. Note that the reward is 0 in any step in which the new assignment is not an improvement over the previous best regardless of whether the quality of the solution is increasing or decreasing. This reward is designed to encourage πθ to yield iteratively improving assignments while being agnostic towards how the assignments change between improvements. Our reward is conceptually similar to that of ECO-DQN [Barrett et al., 2020]. The main difference is that we do not add intermediate rewards for reaching local maxima. Inductively, we observe that the total reward over all iterations is given by ∑Tt=1 r(t) = q(T+1) -QI(α(0) ). For any input instance I the total reward is maximal (relative to QI(α(0) )) if and only if the highest achieved quality q(T+1) is the optimal quality for I. In Appendix C we provide an ablation study where we compare our reward scheme to the simpler choice of using QI(α(t) ) directly as a reward.

Markov Decision Process. For a given input I we model the procedure described so far as a Markov Decision Process M(I) which will allow us to deploy standard reinforcement learning methods for training: The state in iteration t is given by s(t) = (α(t) , q(t) ) and contains the current assignment and highest quality achieved before step t. The initial assignment α(0) is drawn uniformly at random and q(0) = 0. The space of actions A is simply the set of all possible assignments for I. 3 The soft assignments produced by the policy πθ are distributions over this action space. After the next action is sampled from this distribution, the state transition of the MDP is deterministic and updates the state with the chosen assignment and its quality. The reward r(t) at time t is defined as in Equation 3.

Training. During training, we assume that some data generating distribution Ω of CSP instances is given. We aim to find a policy that performs well on this distribution of inputs. Ideally, we need to find the set of parameters θ∗ which maximizes the expected total reward if we first draw an instance from Ω and then apply the model to it for Ttrain ∈ N steps:

3 Formally, the state and action space also contain the recurrent states h(t) which we omit for clarity.

The discount factor λ ∈ (0, 1] and the number of search iterations during training Ttrain are both hyperparameters. Starting with randomly initialized parameters θ, we utilize REINFORCE [Williams, 1992] to train πθ with stochastic policy gradient ascent. REINFORCE is a natural choice for training ANYCSP since its complexity does not depend on the size of the action space A. Soft assignments allow us to efficiently sample the next assignment α ∼ φ and recover its probability P(α|φ) = ∏X φ(α(X)). These are the only operations on the action space required for REINFORCE. Note that we use vanilla REINFORCE without a baseline or critic network and we sample a single trajectory for every training instance. We found this simple version of the algorithm to be surprisingly robust and effective in our setting. Details on how the policy gradients are computed are provided in Appendix A.

4.3 Implementation and Hyperparameters

We implement ANYCSP in PyTorch. The code for relabeling G(I, α(t) ) in each iteration t is also fully based on PyTorch and is GPU-compatible. We implement generalized sparse matrix multiplication in the COO format in CUDA. This helps to increase the memory efficiency and speed of the message passes between values and constraints.

We choose a hidden dimension of d = 128 for all experiments. We train with the Adam optimizer for 500K training steps with a batch size of 25. Training a model takes between 24 and 48 hours, depending on the data. During training, we set the upper number of iterations to Ttrain = 40. During testing, we usually run ANYCSP with a timeout rather than a fixed upper number of iterations T . All hyperparameters are provided in Appendix A.

For each training distribution Ω we implement data loaders that sample new instances on-the-fly in each training step. With our hyperparameters we therefore train each model on 12.5 Million sampled training instances. We use fixed subsets of 200 instances sampled from each distribution before training as validation data. The exact generation procedures for each training distribution are provided in Appendix B.

5 Experiments

We evaluate ANYCSP on a wide range of well-known CSPs: Boolean satisfiability (3-SAT) and its maximisation version (MAX-k-SAT for k = 3, 4, 5), graph colorability (k-COL), maximum cut (MAXCUT) as well as random CSPs (generated by the so-called MODEL RB). These problems are of high theoretical and practical importance and are commonly used to benchmark CSP heuristics. We train one ANYCSP model for each of these problems using randomly generated instances. Recall that the process of learning problem-specific heuristics with ANYCSP is purely data-driven as our architecture is generic and can take any CSP instance as input. We crosscompare all models on each others CSPs in Appendix B.6.

Here, we will compare the performance of ANYCSP to classical solvers and heuristics as well as previous neural approaches. When applicable, we also tune the configuration of the classical algorithms on our validation data to ensure a fair comparison. All neural approaches run with one NVIDIA Quadro RTX A6000 GPU with 48GB of memory. All classical approaches run on an Intel Xeon Platinum 8160 CPU (2.1 GHz) and 64GB of RAM.

MODEL RB. First, we evaluate ANYCSP on general CSP benchmark instances generated by the MODEL RB [Xu and Li, 2003]. Our training distribution ΩRB consists of randomly generated MODEL RB instances with 30 variables and arity 2. The test dataset RB50 contains 50 satisfiable instances obtained from the XCSP project [Audemard et al., 2020]. These instances each contain 50 variables, domains with 23 values and roughly 500 constraints. They are commonly used as part of the XCSP Competition to evaluate state-of-the-art CSP solvers. Note that the hardness of MODEL RB problems comes from the dense, random constraint relations chosen at the threshold of satisfiability and even instances with 50 variables are very challenging. We will compare ANYCSP to three state-of-the-art CSP solvers: Picat [Zhou, 2022], ACE [Lecoutre, 2022] and CoSoCo [Audemard, 2018]. Picat is a SAT-based solver while ACE and CoSoCo are based on constraint propagation. Picat in particular is the winner of the most recent XCSP Competition [Audemard et al., 2022]. No prior neural baseline exists for this problem.

Figure 3 provides a the results on the RB50 dataset. All algorithms run once on each instance with a 20 Minute timeout. ANYCSP solves the most instances by a substantial margin.

The second strongest approach is the CoSoCo solver which solves 34 instances in total, 8 less than ANYCSP. Within the timeout of 20 Minutes, ANYCSP will perform 500K search iterations. Recall that we set Ttrain = 40. Therefore, the learned policy generalizes to searches that are over 10K times longer than those seen during training.

Graph Coloring. We consider the problem of finding a conflict-free vertex coloring given a graph G and number of colors k. The corresponding CSP instance has variables for each vertex, domains containing the k colors and one binary "̸="-constraint for each edge. We train on a distribution ΩCOL of graph coloring instances for random graphs with 50 vertices. We mix Erd˝os-Rényi, Barabási-Albert and random geometric graphs in equal parts. The number of colors is chosen to be in [3, 10]. As test instances we use 100 structured benchmark graphs with known chromatic number X(G). The instances are obtained from a collection of hard coloring instances commonly used to benchmark heuristics 4 . They are highly structured and come from a wide range of synthetic and real problems. We divide the test graphs into two sets with 50 graphs each: COL<10 contains graphs with X(G) < 10 and COL≥10 contains graphs with X(G) ≥ 10. The graphs in COL≥10 have up to 1K vertices, 19K edges and a chromatic number of up to 73. This experiment tests generalization to larger domains and more complex structures.

We compare the performance to three problem specific heuristics: a simple greedy algorithm, the classic heuristic DSATUR [Brélaz, 1979] and the state-of-the-art heuristic HybridEA [Galinier and Hao, 1999], all implemented efficiently by [Lewis et al., 2012; Lewis, 2015]. We also evaluate the best two CSP solvers from the MODEL RB experiment. The neural baseline RUNCSP is also tested on COL<10. Unlike ANYCSP, RUNCSP requires us to fix a domain size before training. Therefore, we must train one RUNCSP model for each tested chromatic number 4 ≤ X(G) ≤ 9 and omit testing on COL≥10. We use the same training data as [Tönshoff et al., 2021] for their experiments on structured coloring benchmarks.

Table 1 provides the number of solved k-COL instances from both splits. ANYCSP is on par with HybridEA which solves the most instances of all baselines. RUNCSP solves significantly fewer instances than ANYCSP on COL<10 and outperforms only the simple greedy approach. ANYCSP solves 40 out of the 50 instances in COL≥10. The optimally colored graphs include the largest instance with 73 colors. Since ANYCSP trains with 3 to 10 colors the trained model is able to generalize to significantly larger domains.

4 https://sites.google.com/site/graphcoloring/vertex-coloring

MAXCUT. For MAXCUT we train on the distribution ΩMCUT of random unweighted Erd˝os-Rényi graphs with 100 vertices and an edge probability p ∈ [0.05, 0.3]. Our test data is Gset [Ye, 2003], a collection of commonly used MAXCUT benchmarks of varying structure with 800 to 10K vertices. We evaluate three neural baselines: RUNCSP, ECO-DQN [Barrett et al., 2020] and ECORD [Barrett et al., 2022]. RUNCSP is also trained on ΩMCUT. We train and validate ECO-DQN and ECORD models with the same data that [Barrett et al., 2022] used for their Gset experiments. We omit S2V-DQN [Khalil et al., 2017] since ECO-DQN and ECORD have been shown to yield substantially better cuts. We adopt the evaluation setup of ECORD and run the neural methods with 20 parallel runs and a timeout of 180s on all unweighted instances of Gset. The results of a standard greedy construction algorithm and the well-known SDP based approximation algorithm by [Goemans and Williamson, 1995] are also included as classical baselines. Both are implemented by [Mehta, 2019]. SDP runs with a 3 hour timeout for graphs with up to 1K vertices.

Table 2 provides results for Gset. We divide the test graphs into groups by the number of vertices (8-9 graphs per group) and report the mean deviation from the best-known cuts obtained by [Benlic and Hao, 2013] for each method. ANYCSP outperforms all baselines across all graph sizes by a large margin. Recall that RUNCSP trains on a soft relaxation of MAXCUT while ECO-DQN and ECORD are both neural local search approaches. Neither concept matches the results of our global search approach trained with policy gradients.

3-SAT. For 3-SAT we choose the training distribution Ω3SAT as uniform random 3-SAT instances with 100 variables. The ratio of clauses to variables is drawn uniformly from the interval [4, 5]. For 3-SAT we test on commonly used benchmark instances for uniform 3-SAT from SATLIB 5 . The test set SLN contains 100 instances with N ∈ {50, 100, 150, 200, 250} variables each. The density of these formulas is at the threshold of satisfiability. We evaluate two neural baselines: RLSAT [Yolcu and Póczos, 2019] and PDP [Amizadeh et al., 2019]. PDP is also trained on Ω3SAT. We train RLSAT with the curriculum learning dataset for 3-SAT provided by its authors. We also adopt the experimental setup of RLSAT, which limits the evaluation run by the number of search steps instead of a timeout. The provided code for both PDP and RLSAT is comparatively slow and a timeout would compare implementation details rather than the capability of the learned algorithms. We also evaluate two conventional local search heuristics: The classical WalkSAT algorithm [Selman et al., 1993] based on random walks and a modern probabilistic approach called probSAT [Balint and Schöning, 2018]. Like [Yolcu and Póczos, 2019], we apply stochastic boosting and run each method 10 times for 10K steps on every instance. PDP is deterministic and only applied once to each formula. Note that our aim is to compare the performance of ANYCSP to prior end-2-end neural approaches and conventional stochastic search algorithms for SAT. We note that ANYCSP can not currently compete with CDCL solvers on structured decision SAT instances, like most known stochastic search heuristics.

5 https://www.cs.ubc.ca/~hoos/SATLIB/benchm.html

Table 3 provides the number of solved instances for each tested size. All compared approaches do reasonably well on small instances with 50 variables. However, the performance of the two neural baselines drops significantly as the number of variables increases. ANYCSP does not suffer from this issue and even outperforms the classical local search algorithms on the three largest instance sizes considered here.

MAX-k-SAT. We train on the distribution ΩMSAT of uniform random MAX-k-SAT instances with 100 variables and k ∈ {3, 4}. Here, the clause/variable ratio is chosen from [5, 8] and [10, 16] for k = 3 and k = 4, respectively. These formulas are denser than those of Ω3SAT since we aim to train for the maximization task. Our test data for MAX-k-SAT consists of uniform random k-CNF formulas generated by us. For each k ∈ {3, 4, 5} we generate 50 instances with 10K variables each. The number of clauses is chosen as 75K for k = 3, 150K for k = 4 and 300K for k = 5. These formulas are therefore 100 times larger than the training data and aim to test the generalization to significantly larger instances as well as unseen arities, since k = 5 is not used for training. Neural baselines for SAT focus primarily on decision problems. For MAX-k-SAT we therefore compare ANYCSP only to conventional search heuristics: the classical (Max-)WalkSAT [Selman et al., 1993] and two state-of-the-art MAX-SAT local search heuristics CCLS [Luo et al., 2015] and SATLike [Cai and Lei, 2020]. Table 4 provides a comparison. We provide the mean number of unsatisfied clauses after processing each instance with a 20 Minute timeout. Remarkably, ANYCSP outperforms all classical baselines by a significant margin. We note that for each tested arity ANYCSP finds the best solution on all 50 test instances.

We point out that the conventional search heuristics all perform over 100M search steps in the 20 Minute timeout. ANYCSP performs less than 100K steps on each instance in this experiment. The GNN cannot match the speed with which classical algorithms iterate, even though it is accelerated by a GPU. Despite this, ANYCSP consistently finds the best solutions. Figure 4 evaluates this surprising observation further. We plot the number of unsatisfied clauses in the best found solution against the search step in which the solution was found (Steps to Opt.) for all methods and all instances of our MAX-5-SAT test data. We also provide the results of a modified ANYCSP version (ANYCSP Local defined in Appendix C) that is only allowed to change one variable at a time and is therefore a local search heuristic. Note that the x-axis is logarithmic as there is a clear dichotomy separating neural and classical approaches: Compared to conventional heuristics ANYCSP performs roughly three orders of magnitude fewer search steps in the same amount of time. When restricted to local search, ANYCSP is unable to overcome this deficit and yields worse results than strong heuristics such as SATLike. However, when ANYCSP leverages global search to parallelize refinements across the whole instance it can find solutions in 100K steps that elude state-of-the-art local search heuristics after well over 100M iterations.

6 Conclusion

We have introduced ANYCSP, a novel method for neural combinatorial optimization to learn heuristics for any CSP through a purely data-driven process. Our experiments demonstrate how the generic architecture of our method can learn effective search algorithms for a wide range of problems. We also observe that standard policy gradient descent methods like REINFORCE are capable of learning on an exponentially sized action space to obtain global search heuristics for NPhard problems. This is a critical advantage when processing large problem instances.

Directions for future work include widening the scope of the architecture even further: Weighted and partial CSPs are a natural extension of the CSP formalism and could be incorporated through node features and adjustments to the reward.