Constraint Satisfaction

Follow this topic Ask about this topic

Constraint satisfaction models problems with variables, possible values, and rules that determine which combinations are allowed, helping solve tasks such as scheduling, graph coloring, and Sudoku. Classical approaches include constraint propagation and backtracking, often combined with SAT, SMT, constraint programming, or integer programming solvers. Recent work also uses graph neural networks, diffusion models, and language models to propose assignments or guide search, frequently pairing them with symbolic verification and repair. A central challenge is making learned methods reliable on genuinely hard instances and robust to changes in problem size, representation, or wording, while matching the efficiency and guarantees of classical solvers.

Latest papers

86 papers10 papers in the last four weeks, up 43% on the four weeks before. 0.1% of all new papers.

Unsat Core Prediction through Polarity-Aware Representation Learning over Clause-Literal Hypergraphs
May 6, 2026Zhenchao Sun, Shuai Ma, Ping Lu +1Hypergraph Neural Networks Constraint Satisfaction
SKLCCSE Lab, Beihang University, Beijing, China.
Residual Drift Dominates Contradiction in Multi-Turn Constraint Reasoning
Apr 28, 2026Sebastien KawadaConstraint Satisfaction
Kaons Los Angeles, United States
Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning
Apr 25, 2026Akihiro Takemura, Katsumi Inoue, Masaaki NishinoSymbolic Reasoning Constraint Satisfaction
National Institute of Informatics, Tokyo, Japan · Communication Science Laboratories, NTT, Inc., Japan
HardNet++: Nonlinear Constraint Enforcement in Neural Networks
Apr 21, 2026Andrea Goertzen, Kaveh Alim, Youngjae Min +1Nonlinear MPC Neural Network Optimization
Massachusetts Institute of Technology
Transfer Learning from Foundational Optimization Embeddings to Unsupervised SAT Representations
Apr 16, 2026Koyena Pal, Serdar KadiogluUnsupervised Representation Learning Transfer Learning
AI Center of Excellence, Fidelity Investments, USA · Khoury College of Computer Sciences, Northeastern University, USA · Department of Computer Science, Brown University, USA
Empirical Evidence of Complexity-Induced Limits in Large Language Models on Finite Discrete State-Space Problems with Explicit Validity Constraints
Apr 15, 2026Md. Fahad Ullah Utsho, Mohd. Ruhul Ameen, Akif Islam +2LLM Evaluation Large Reasoning Models
Department of Information and Communication Engineering, University of Rajshahi, Bangladesh · College of Engineering and Computer Sciences, Marshall University, Huntington, WV, USA · Department of Computer Science and Engineering, University of Rajshahi, Bangladesh
Learning Hierarchical and Geometry-Aware Graph Representations for Text-to-CAD
Apr 11, 2026Shengjie Gong, Wenjie Peng, Hongyuan Chen +5Text-to-CAD Generation Program Synthesis
South China University of Technology · Zhuzhou CRRC Times Electric Co., Ltd. · Guangdong University of Technology
Hypergraph Neural Networks Accelerate MUS Enumeration
Apr 10, 2026Hiroya Ijima, Koichiro YawataConstraint Satisfaction
Hitachi, Ltd.
SatIR: Scalable High-Recall Constraint-Satisfaction-Based Information Retrieval for Clinical Trials Matching
Apr 10, 2026Zikai Zhou, Yufei Jin, Yilin Xu +3Healthcare Satisfiability Modulo Theories
Department of Computer Science, Stanford University, Stanford, CA, USA · Samueli Electrical and Computer Engineering, UCLA, Los Angeles, CA, USA · Department of Computer Science, Emory University, Atlanta, GA, USA +1
A Quantum Search Approach to Magic Square Constraint Problems with Classical Benchmarking
Apr 6, 2026Rituparna R, Harsha Varthini, Aswani Kumar CherukuriConstraint Satisfaction
School of Computer Science Engineering and Information Systems, Vellore Institute of Technology, Vellore 632014, India
GaloisSAT: Differentiable Boolean Satisfiability Solving via Finite Field Algebra
Mar 25, 2026Curie Kim, Carsten Portner, Mingju Liu +6Boolean Satisfiability Constraint Satisfaction
University of Maryland, College Park, MD, USA. · NVIDIA Research, Santa Clara, CA, USA. · NVIDIA Research, Austin, TX, USA. +3
Large Neighborhood Search meets Iterative Neural Constraint Heuristics
Mar 21, 2026Yudong W. Xu, Wenhao Li, Scott Sanner +1Constraint Satisfaction Large Neighborhood Search
Department of Mechanical & Industrial Engineering, University of Toronto · Vector Institute
Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems
Mar 21, 2026Alankrita Bhatt, Mukur Gupta, Germain Kolossov +1Diffusion Sampling Diffusion Models
Granica Computing Inc. – granica.ai · Stanford University
AS2 -- Attention-Based Soft Answer Sets: An End-to-End Differentiable Neuro-Soft-Symbolic Reasoning Architecture
Mar 19, 2026Wael AbdAlmageedNeuro-Symbolic Reasoning Constraint Satisfaction
Clemson University
Domain-Independent Dynamic Programming with Constraint Propagation
Mar 17, 2026Imko Marijnissen, J. Christopher Beck, Emir Demirović +1Resource-Constrained Project Scheduling Constraint Propagation
Delft University of Technology, The Netherlands · University of Toronto, Canada · National Institute of Informatics, Japan +1
Learning to Rank the Initial Branching Order of SAT Solvers
Mar 7, 2026Arvid Eriksson, Gabriel Poesia, Roman Bresson +2Boolean Satisfiability Constraint Satisfaction
KTH Royal Institute of Technology · Kempner Institute at Harvard University · Mohamed Bin Zayed University of Artificial Intelligence
Pencil Puzzle Bench: A Benchmark for Multi-Step Verifiable Reasoning
Mar 2, 2026Justin WaughLLM Evaluation LLM Reasoning
Approximate Labs
Denotational Semantics for ODRL: Knowledge-Based Constraint Conflict Detection
Feb 23, 2026Daham Mustafa, Diego Collarana, Yixin Peng +4Policy Evaluation Knowledge Representation
RWTH Aachen University, Germany · Fraunhofer FIT, Sankt Augustin, Germany · University of Galway, Ireland
Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems
Feb 20, 2026Geri Skenderi, Lorenzo Buffoni, Francesco D'Amico +6Constraint Satisfaction Neural Combinatorial Optimization
Department of Computing Sciences, Bocconi University, Milan, Italy · Bocconi Institute for Data Science and Analytics (BIDSA) · Department of Physics and Astronomy and INFN, University of Florence +4
Differentiable Symbolic Planning: A Neural Architecture for Constraint Reasoning with Learned Feasibility
Feb 19, 2026Venkatakrishna Reddy OrugantiNeuro-Symbolic Planning Neuro-Symbolic Reasoning
Sithara Inc., Plano, Texas, USA
Implementing Cumulative Functions with Generalized Cumulative Constraints
Aug 3, 2025Pierre Schaus, Charles Thomas, Roger KameugneConstraint Propagation Constraint Satisfaction
UCLouvain, ICTEAM, Louvain-la-Neuve, Belgium · University of Maroua, Maroua, Cameroon
3D Software Synthesis Driven by Constraint-Expressive Intermediate Representation
Jul 24, 2025Shuqing Li, Anson Y. Lam, Yun Peng +2Program Synthesis 3D Scene Generation
The Chinese University of Hong Kong Hong Kong, China · Renmin University of China Beijing, China
HardCore Generation: Generating Hard UNSAT Problems for Data Augmentation
Sep 27, 2024Joseph Cotnareanu, Zhanguang Zhang, Hui-Ling Zhen +2Synthetic Data Augmentation Synthetic Benchmark Generation
McGill University Montreal, Canada · Huawei Noah’s Ark Lab Montreal, Canada · Huawei Noah’s Ark Lab Hong Kong, China +1
Stable Marriage Problems with Ties and Incomplete Preferences: An Empirical Comparison of ASP, SAT, ILP, CP, and Local Search Methods
Aug 11, 2021Selin Eyupoglu, Muge Fidan, Yavuz Gulesen +5Answer Set Programming Constraint Satisfaction
Computer Science, Faculty of Engineering and Natural Sciences, Sabanci University, Istanbul, Turkey · Economics, Faculty of Arts and Social Sciences, Sabanci University, Istanbul, Turkey
PyCSP3: Modeling Combinatorial Constrained Problems in Python
Sep 1, 2020Christophe Lecoutre, Nicolas SzczepanskiConstrained Optimization Constraint Satisfaction
University of Artois CRIL CNRS, UMR 8188[cs.AI] France
A binarized-domains arc-consistency algorithm for TCSPs: its computational analysis and its use as a filtering procedure in solution search algorithms
Feb 22, 2020Amar IsliConstraint Satisfaction Temporal Consistency
University of Sciences and Technology Houari Boumedi`ene · Faculty of Computer Science · Department of Artiﬁcial Intelligence and Data Science +2

May 6, 2026J/K move · Enter open · S save

Unsat Core Prediction through Polarity-Aware Representation Learning over Clause-Literal Hypergraphs

Zhenchao Sun, Shuai Ma, Ping Lu, Chongyang Tao

SKLCCSE Lab, Beihang University, Beijing, China.

Hypergraph Neural Networks Constraint Satisfaction Invariant Representation Learning Boolean Satisfiability

Open paper AskPDF arXiv

Graph neural networks have been widely used in Boolean satisfiability (SAT) tasks to learn structural information from SAT formulas. The goal of these studies is to solve SAT instances or to enhance SAT solvers, including tasks such as unsat-core prediction. However, most existing approaches model a SAT formula as a bipartite graph or a directed acyclic graph, which are less direct in capturing clause-level and higher-order interactions among literals and clauses. Moreover, these approaches are limited in modeling intrinsic polarity-related properties of SAT, such as the complementary relationship between the positive and negative literals of a variable. To address these limitations, we propose a polarity-aware representation learning framework over clause-literal hypergraphs. We model SAT formulas as clause-literal hypergraphs augmented with a clause incidence graph to capture higher-order structural interactions. We then introduce a polarity-aware decomposition mechanism that separates variable representations into polarity invariant and equivariant components, explicitly modeling the relationship between positive and negative literals, with the resulting literal representations propagated along the hypergraph structure. We further incorporate a polarity-inversion consistency regularization to reinforce polarity-consistent representations during training. Experimental results on multiple SAT datasets demonstrate the effectiveness of the proposed approach.