Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction

We appreciate your thoughtful comments and are glad that you see the potential for our method in aiding the development of large-scale CSP solving.

no discussion about RL-based methods both in theoretical analysis and experimental comparison.

We would like to clarify that both theoretical and experimental comparisons with RL-based approaches are included in the paper.

• Theoretical considerations are discussed in Sections 2.2 and 3.3.
• Experimentally, we directly compare against ANYCSP, a state-of-the-art RL-guided neural solver for CSPs.

We will revise the paper to make these points more prominent.

The reward signal in this setting seems much easier to define. For instance, we could simply set the reward as the difference in the number of satisfied constraints.

Defining a reward as the number of satisfied constraints is indeed an intuitive design. However, prior work indicates that such rewards are not sufficient to guide learning effectively.

ANYCSP [1] experimented with the exact reward you have suggested and found that “models trained with this reward tend to get stuck in local maxima”. They comment that “intuitively, this simple reward scheme immediately punishes the policy for stepping out of a local maximum causing stagnating behavior”.

Their method implements a much sparser reward to avoid this issue by setting the reward to 0 in any step in which the new assignment is not an improvement over the previous best.

In contrast, our approach provides a dense training signal through differentiable penalty functions. These loss functions guide the model even when no constraint is fully satisfied.

[1] Tönshoff, Jan, et al. "One model, any CSP: graph neural networks as fast global search heuristics for constraint satisfaction." (2022).

Comparison to other methods is not fair. Du et al. (2024) do this experiment based on ResNet.

We note that Du et al. themselves compare against models like SATNet and RRN which are not ResNet based models. SATNet is a model that learns the SDP relaxation of a SAT formulation, while RRN is a graph-based model.

While it’s true that Du et al.’s method uses a ResNet base model, We follow standard practice and make comparisons between full frameworks for solving CSPs.

can this optimization approach also be applied to directly solve Constraint Satisfaction Problems (CSP) using local search?

Yes! And indeed the existing literature of local search was a prominent inspiration for us, specifically, our approach is grounded in principles from the constraint-based local search literature [2]. In this approach, constraints are associated with “violation degrees” that measure how far a solution is from satisfying the constraint (violation = 0 ⇔ satisfied). We adopt this principle and extend it to the neural domain by designing differentiable approximations of these violations that work with probabilistic assignments.

[2] Michel, L., Hentenryck, P.V. (2018). Constraint-Based Local Search. In: Martí, R., Pardalos, P., Resende, M. (eds) Handbook of Heuristics.

Furthermore, can iterative improvement be achieved by addressing an optimization problem with Stochastic Gradient Descent (SGD)?

This is a great insight. Indeed if we ignore the transformer architecture and perform SGD on a set of variable assignments guided by our self-supervised loss, the variable assignments can be updated to become a (relaxed) satisfying solution. However, we found that in practice this method often leads to local optima, furthermore, we see a drastic decrease in performance as the SGD focus on a single instance and does not know how to generalize to other instances. Our framework essentially learns this update using a single-step transformer and is able to generalize by training on a larger set of instances.

To showcase this, we run a simple SGD on a Sudoku board where the missing values are randomly initialized and update it with SGD guided by the loss function for 10000 iterations. We observe the following results averaged over 10 runs:

We see as the problem becomes harder with more missing cells, the number of satisfied alldifferent constraints became lower. We will include this discussion in the revision of the paper.

Thank you for the thoughtful feedback and questions. We’ve conducted new experiments and clarified key aspects of the method in response to your concerns, which we believe strengthen the submission significantly.

Can the authors benchmark on more complicated problems?

We have added experiments on the MAXCUT problem. Please refer to our response to reviewer tcHx for details.

CP-SAT takes more time than learning-based methods, so the authors should consider allowing CP-SAT to solve for longer.

Efficiency is indeed a major advantage of our method and in many applications it is necessary to solve for a good feasible solution very quickly.

That said, we conducted new experiments where CP-SAT was allowed to run for 30 and 60 seconds on the Graph-Coloring task with 10 colors (where ConsFormer had previously outperformed it under 10s). Results are shown below:

We see that CP-SAT can outperform our method on small instances (nodes=100) with extended time, but it still underperforms on larger instances (nodes=200), even with 6x more time. Furthermore, in the new MAXCUT problem, 20 parallel runs–each with 180s limit–were used to compute the results. ConsFormer also outperforms OR-Tools by a significant margin.

compare with more heuristic baselines

We include 3 additional heuristic baselines for graph coloring:

• Greedy Coloring
• Feasibility Jump
• Random Search

The first is the greedy coloring algorithm implemented by networkx and the other two are local search approaches implemented by OR-Tools. We note that the LS algorithms are already present in the default OR-Tools used for the paper.

We observe that while the local-search based heuristics were able to perform well on the smaller instances, their performance significantly worsens on the larger instances with 10 colors.

nurse scheduling results

They were reported in-text in Section 4.3. We will revise the paper for better clarity.

I’m concerned that the paper may lack novelty.

As far as we know, we are the first to successfully apply a Transformer architecture to solve general CSPs in a self-supervised setting. Existing work often requires graph representations of the problems while we treat them as sequences.

How did you decide the lambda_i? Would an adaptive way to select different lambda_i l for different constraints lead to better performance?

This is a great suggestion and an adaptive lambda is indeed an interesting direction that we plan on exploring for future work. For now, each problem has a relatively simple mixture of constraints, so the weights are manually set.

Instead of the differentiable loss with GumbelSoftmax, I wonder if the authors have tried reinforcement learning?

We apologize if we have misunderstood, but we believe the reviewer may be referring to use of the REINFORCE trick (or score-function based gradient estimators) from RL that can be generally used to compute gradients of discrete variables. However, we note that the Gumbel-Softmax paper[1] discusses that this gradient estimator has high variance (Section 3.2 of [1]) and performs very poorly (Section 4.1 of [1]) in practice -- in fact it is the worst performing of all discrete gradient estimators they compare.

[1] Jang et al. "Categorical Reparameterization with Gumbel-Softmax."

instead of feeding the entire solution back for refinement, have the authors consider only improving a subpart of the solution and fixing the rest

We completely agree with the intuition, and in fact, our model effectively incorporates this idea via the Variable Subset Selection step (Section 3.2, line 203). At each iteration, only a subset of variables is selected for update, mimicking local search behavior. We found that this strategy significantly improves generalization compared to updating the full assignment each time, as discussed in Section 4.4.

We sincerely appreciate the encouraging feedback and thoughtful comments.

self-supervision is more limited because it needs support for every constraint to be differentiable.

You're absolutely right to point out that a key limitation of the self-supervised approach is the need to define differentiable approximations for each constraint. As you noted, our method draws directly from the constraint-based local search literature [1], where constraint violations are quantified using "violation degrees" to guide iterative improvement. Our contribution builds on this idea by adapting it into a differentiable, neural-friendly form that allows gradient-based learning.

[1] Michel, L., Hentenryck, P.V. (2018). Constraint-Based Local Search. In: Martí, R., Pardalos, P., Resende, M. (eds) Handbook of Heuristics.

In CSP practice there are more complex and larger datasets available, put a test on the scalability of the approach.

This is a valuable point and was also raised by other reviewers. In response, we have added new experiments on the MAXCUT problem (see our response to Reviewer tcHx). These instances include thousands of variables and constraints and serve as a stronger test of scalability. The results indicate that ConsFormer remains competitive, even under larger problem sizes. While our ultimate goal is to apply ConsFormer to a wide range of CSPs, we believe that the experimental results on four benchmark problems with different combinatorial structures provide ample evidence for the promise of our method.

The results for nurse scheduling were a bit lost in the text

Thank you for raising this, we will revise the paper to highlight the results better.

Have you evaluated the performance when decomposing the global constraints? How does the model balance having more variables vs more complex global constraints to learn?

This is an excellent question. To investigate, we conducted an additional experiment on Sudoku where the all-different constraints are decomposed to pairwise inequalities (36 inequality constraints per all-different). This can be effectively achieved by defining the continuous penalty as follows: $AllDifferent(x_1, \ldots, x_n) \rightarrow \sum_{i\neq j, i< j} \left( \sum_{k} x_i^{(k)}\cdot x_j^{(k)} \right)$ We present the instance solved percentage below:

Interestingly, we observe that in this case, decomposing the constraints does not significantly affect performance which suggests that the model can equally handle a larger number of simpler constraints. However, we note that the resulting number of constraints is still relatively small after decomposing alldifferent for sudoku. Other more complex problems with global constraints may reveal different trade-offs which we leave for future work.

Can you transfer learn, i.e. pretrain the model for individual constraints first and then merge them towards more complex problems?

This is a great insight and is something we are planning as a future direction! One limitation of our current approach (as well as other neural approaches) is the need to train a new model for a new problem domain that consists of a different combination of constraints. With the success of the transformer’s pre-train + fine-tune approach in the natural language setting [2], one could imagine this approach applied to our setting, where models are first pre-trained for all constraints, then combined modularly to be fine-tuned for new problems. Despite the potential promise of this direction, there are many open questions to resolve in future work in order to bridge from the current model to this ideal goal of a highly general and transferable pretrained model. We will add this excellent future work discussion on revision.

[2] Radford, Alec, et al. "Improving language understanding by generative pre-training." (2018).

We greatly appreciate your thorough feedback and have conducted new experiments which we believe have substantially improved the paper.

Additional benchmark.

We have adapted ConsFormer for MAXCUT based on your suggestion.

• MAXCUT is the problem of partitioning nodes of a graph into two sets in a way that maximizes the size of the cut.
• Following ANYCSP, we train on graphs with 100 vertices and test on GSET instances with 800 to up to 10000 vertices.

We report the absolute and relative gap (in percentage) to best known values:

We observe that while ANYCSP remains the best performing approach on GSET, ConsFormer achieves a relative gap of 0.31% to 1.27% on average without extensive model tuning, showcasing its ability to scale up to larger problems with thousands of constraints.

ablation study on the Gumbel-Softmax.

We chose Gumbel-Softmax for its differentiable sampling of discrete variables, aligning with the discrete nature of CSPs. Experiments during development showed it outperformed standard softmax, which we confirmed through a more systematic ablation below.

However, your question prompted us to further investigate why Gumbel-Softmax helps: is it the stochasticity introduced by the Gumbel noise, or simply the sharper outputs it produces? To investigate this, we ran additional experiments using softmax with added temperature control – a variant we had not systematically explored in earlier versions ($Softmax_\tau(z_i) = \frac{\exp\left(z_i / \tau\right)}{\sum_{j} \exp\left(z_j / \tau\right)}$ ), and present the results below (for Sudoku/Graph Coloring, we show the % instances solved, MAXCUT reports the absolute gap to best known values):

Interestingly, softmax with temperature yielded similar or better results than Gumbel-Softmax on problems with smaller sizes, while performing worse on larger problems from MAXCUT. This suggests that while the sharper distributions indeed boost model performance, the stochasticity allows the model to generalize better across larger problem instances. The randomness can promote diversity in intermediate solutions which may help the model escape local optima over multiple inference steps. We will include this ablation in the updated paper.

additional references

We appreciate the extensive list of references and will include them accordingly. We note that this list of references echoes our own finding which is that most existing approaches focus on graph-based representations or SAT formulations. To the best of our knowledge, Transformers have not been effectively implemented for general form CSPs.

constraint violation functions seems ad-hoc and merits more discussion in the paper.

Our approach is grounded in principles from the constraint-based local search literature in CP [1]. Here, constraints are associated with “violation degrees” where violation degree = 0 ⇔ satisfied. Specific functions to evaluate violation degrees are designed for different global constraints.

Selecting the design for the continuous penalty is indeed important. During development we experimented with various continuous approximations including some inspired by recent work using T-norm [2] and Entropy [3] with varying effectiveness.

However, our goal is to showcase the effectiveness of the self-supervised approach combined with the single-step transformer. We view the choice of continuous penalty functions as a flexible and modular component of our framework, one that can benefit from further improvements, but is not the central focus of this work. We will include more discussion on this in the updated paper.

[1] Michel, L., Hentenryck, P.V. (2018). Constraint-Based Local Search. In: Martí, R., Pardalos, P., Resende, M. (eds) Handbook of Heuristics.

[2] Giannini, Francesco, et al. “T-norms driven loss functions for machine learning.”

[3] Chen, Di, et al. “Deep reasoning networks: Thinking fast and slow.”