Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction
This addresses the challenge of accelerating CSP solutions for applications in scheduling and optimization, offering a more efficient alternative to supervised or reinforcement learning methods.
The paper tackles Constraint Satisfaction Problems (CSPs) by proposing ConsFormer, a self-supervised Transformer framework that iteratively refines solutions without requiring feasible labeled data or complex rewards, achieving results on Sudoku, Graph Coloring, Nurse Rostering, and MAXCUT, including handling out-of-distribution CSPs through additional iterations.
We present a Transformer-based framework for Constraint Satisfaction Problems (CSPs). CSPs find use in many applications and thus accelerating their solution with machine learning is of wide interest. Most existing approaches rely on supervised learning from feasible solutions or reinforcement learning, paradigms that require either feasible solutions to these NP-Complete CSPs or large training budgets and a complex expert-designed reward signal. To address these challenges, we propose ConsFormer, a self-supervised framework that leverages a Transformer as a solution refiner. ConsFormer constructs a solution to a CSP iteratively in a process that mimics local search. Instead of using feasible solutions as labeled data, we devise differentiable approximations to the discrete constraints of a CSP to guide model training. Our model is trained to improve random assignments for a single step but is deployed iteratively at test time, circumventing the bottlenecks of supervised and reinforcement learning. Experiments on Sudoku, Graph Coloring, Nurse Rostering, and MAXCUT demonstrate that our method can tackle out-of-distribution CSPs simply through additional iterations.