Reproduce “Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction” on OpenResearch

About this paper

Yudong W. Xu, Wenhao Li, Scott Sanner, Elias B. Khalil

ConsFormer, a self-supervised Transformer, iteratively refines variable assignments for Constraint Satisfaction Problems (CSPs) by minimizing differentiable constraint violation penalties. This approach demonstrates improved generalization to out-of-distribution instances, achieving a 77.74% solve rate on hard Sudoku instances and competitive performance on Graph Coloring and Nurse Scheduling benchmarks.

Key insights

• Self-supervised learning with differentiable constraint penalties offers an effective and scalable method for training neural networks to solve CSPs, bypassing limitations of supervised and reinforcement learning.
• Iterative application of a single-step trained Transformer at inference time significantly enhances generalization capabilities, allowing the model to solve out-of-distribution and harder problem instances.
• The inclusion of relative positional encodings for constraint relations and stochastic variable selection are crucial for the Transformer to capture problem structure and effectively explore the solution space, avoiding local optima.

Summary by alphaXiv.