Constraint Programming

Also known as CP

Constraint programming represents a problem with variables, domains, and constraints, then searches for assignments that satisfy the rules or optimize an objective. Solvers combine propagation, which prunes impossible values, with branching, global constraints for structures such as scheduling and routing, and methods such as SAT/ILP integration or logic-based Benders decomposition. Applications include resource and workforce scheduling, routing, timetabling, and configuration, where complex rules make flexible models useful. Current work explores stronger propagation, hybrid and learned search, and AI-assisted modeling; a central challenge is improving performance while keeping models and results correct and verifiable.

Latest papers

38 papers4 papers in the last four weeks, up 33% on the four weeks before. 0.0% of all new papers.

Solving Flood-It Puzzles: A Comparison of Tailored A* Search with Declarative Solver Approaches
Oct 22, 2026Philipp von Manteuffel, Benjamin BlankertzTree Search Constraint Programming
Chair for Neurotechnology Technische Universität Berlin
Learning Size Independent Constraint Models from Input Data and Positive and Negative Example Solutions
Oct 9, 2026Helmut SimonisConstraint Programming Constraint Satisfaction
School of Computer Science and Information Technology, University College Cork, Ireland
Using Weisfeiler-Leman Features for Algorithm Selection in Constraint Optimisation
Oct 8, 2026Alessio Pellegrino, Jacopo MauroAlgorithm Selection Constraint Programming
University of Southern Denmark, Denmark
Agentic AI-Assisted Modeling for Production Scheduling: Assessment in Constraint Programming
Oct 7, 2026Ángel Sánchez-Fernández, Javier Pernas-Álvarez, Diego Crespo-PereiraNatural Language to Optimization Modeling Combinatorial Optimization
Universidade da Coru˜na, Campus Industrial de Ferrol, CITENI, Grupo Integrado de Ingenier´ıa, Esteiro s/n, Ferrol, 15403.
Learning Symbolic Constraint Representations from Examples: A Neuro-Symbolic Approach
Sep 10, 2026Nassim Belmecheri, Arnaud Gotlieb, Nadjib Lazaar +1Symbolic Reasoning Neurosymbolic Learning
Simula Research Laboratory, Oslo, Norway · Microsoft, Norway · LISN, CNRS, Paris-Saclay University, France
frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study
Sep 2, 2026Onur UğurluCombinatorial Optimization Metaheuristic Optimization
İzmir Bakırçay University
From Metaheuristics to Exact Methods: A CP-SAT Approach for Multi-Objective Healthcare Workforce Scheduling
Aug 31, 2026Vipul Patel, Anirudh Deodhar, Dagnachew BirruHealthcare Multi-Objective Optimization
1Phi Labs, Quantiphi
Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions
Aug 19, 2026Shrenil Shaun Sharma, Avi SharmaLarge Language Model-Guided Optimization Combinatorial Optimization
Independent Researcher San Francisco, CA, USA · Department of Electrical Engineering and Computer Sciences University of California, Berkeley
Translating finite-domain integer constraint models to CP/SMT/ILP/PB/SAT solvers with CPMpy
Aug 15, 2026Tias Guns, Ignace Bleukx, Hendrik Bierlee +8Constraint Programming Constraint Satisfaction
KU Leuven, Belgium · Nonfiction Software, Belgium · Flanders Make, Belgium +2
LLM-Guided Graph Generation for Structure-Based Local Improvement Methods
Aug 13, 2026Hai Xia, Vaidyanathan Peruvemba Ramaswamy, Stefan SzeiderAutomated Heuristic Design Metaheuristic Optimization
Algorithms and Complexity Group, TU Wien, Austria
Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming
Aug 11, 2026Alessandro Bertagnon, Marco GavanelliTraveling Salesperson Problem Constraint Propagation
Department of Environmental and Prevention Sciences, University of Ferrara, Italy · Department of Engineering, University of Ferrara, Italy
Improving Constraint Models with LLM Agents
Aug 8, 2026Florentina Voboril, Stefan SzeiderLarge Language Model-Guided Optimization Combinatorial Optimization
Algorithms and Complexity Group TU Wien, Vienna, Austria
LeanCSP: A Framework for Certifying Constraint Reformulation and Solving in Lean
Jul 30, 2026Pablo Manrique, Stefan SzeiderSymmetry Breaking Formal Verification
Algorithms and Complexity Group TU Wien, Vienna, Austria
LLM-Guided Evolutionary Search for Constraint Model Reformulation to Improve Solver Efficiency
Jul 30, 2026Kostis Michailidis, Dimos Tsouros, Nguyen Dang +1Automated Heuristic Design Evolutionary Optimization
1DTAI, KU Leuven, Belgium · University of Western Macedonia, Greece · University of St Andrews, United Kingdom
Global Difference Constraint Propagation for Constraint Programming
Jul 22, 2026Lucas Kletzander, Jip J. Dekker, Andreas Schutt +1Constraint Propagation Constraint Satisfaction
1Databases and Artificial Intelligence Group, TU Wien, Karlsplatz 13, Wien, 1040, Austria. · Department of Data Science and Artificial Intelligence, Monash University, Clayton, 3168, Victoria, Australia. · 3ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA), Melbourne, Victoria, Australia. +1
SEER: Supervised Learning to Control Energetic Reasoning
Jul 17, 2026Sascha Van Cauwelaert, Michele Lombardi, Pierre SchausConstraint Propagation Constraint Satisfaction
Universit´e Catholique de Louvain · Universit`a di Bologna
EZSMT Version 3, Matured
Jul 15, 2026Yuliya LierlerAnswer Set Programming Constraint Programming
University of Nebraska Omaha, USA
CP-WSP: A Declarative CP-SAT Framework for Configurable Multi-Constraint Workforce Scheduling
Jul 6, 2026Vipul Patel, Anirudh Deodhar, Dagnachew BirruMulti-Objective Optimization Constraint Programming
Phi Labs, Quantiphi
Learning Splitting Heuristics for Parallel String Solvers
Jun 9, 2026Chenhao Gao, Peisen YaoAutomated Algorithm Discovery Automated Heuristic Design
The State Key Laboratory of Blockchain and Data Security, Zhejiang University Hangzhou, China
Robust Asynchronous Planning via Auto-Formalization
May 31, 2026Jiayi Zhang, Jianing Yin, Ben Zhou +1LLM Planning Symbolic Planning
Drexel University · Arizona State University
CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem
May 22, 2026Emma Legrand, Roger Kameugne, Pierre SchausDynamic Programming Combinatorial Optimization
ICTEAM, UCLouvain, Belgium
Streamlined Constraint Reasoning via CNN Pattern Recognition on Enumerated Solutions
May 19, 2026Patrick SpracklenLLM-Based Program Synthesis Constraint Satisfaction
Transforming Constraint Programs to Input for Local Search
May 19, 2026Jo Devriendt, Patrick De Causmaecker, Marc DeneckerCombinatorial Optimization Local Search
University of Leuven
PyCSP3-Scheduling: A Scheduling Extension for PyCSP3
May 14, 2026Sohaib AfifiConstraint Programming
Univ. Artois, UR 3926, Laboratoire de Génie Informatique et d’Automatique de l’Artois (LGI2A), F-62400 Béthune, France
A Constraint Programming Approach for n-Day Lookahead Playoff Clinching in the NHL
May 13, 2026Gili Rosenberg, Kyle E. C. Booth, J. Kyle Brubaker +1Sports Analytics Constraint Programming
Amazon Advanced Solutions Lab, Seattle, WA, 98170, USA
Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers
May 12, 2026Haoyu Wang, Yuliang Song, Tao Li +5Large Language Model-Guided Optimization LLM-Based Program Synthesis
University of Pennsylvania · University of Toronto · Google DeepMind +1
MathConstraint: Automated Generation of Verified Combinatorial Reasoning Instances for LLMs
May 8, 2026Viresh Pati, Zhengyu Li, Piyush Jha +3Mathematical Reasoning Benchmarks Synthetic Benchmark Generation
Georgia Institute of Technology, USA · KNOWIDEA Technologies
Optimal Counterfactual Search in Tree Ensembles: A Study Across Modeling and Solution Paradigms
May 7, 2026Awa Khouna, Youssouf Emine, Julien Ferry +1Counterfactual Explanations Mixed-Integer Linear Programming
Polytechnique Montréal · Ivey Business School
CP-SynC: Multi-Agent Zero-Shot Constraint Modeling in MiniZinc with Synthesized Checkers
May 3, 2026Yuliang Song, Eldan CohenMulti-Agent LLM Systems LLM-Based Program Synthesis
Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Canada
Text2Model: Modeling Copilots for Text-to-Model Translation
Apr 14, 2026Serdar Kadioglu, Karthik Uppuluri, Akash SingirikondaNatural Language to Optimization Modeling Large Language Model-Guided Optimization
AI Center of Excellence, Fidelity Investments · Department of Computer Science, Brown University

Oct 22, 2026J/K move · Enter open · S save

Solving Flood-It Puzzles: A Comparison of Tailored A* Search with Declarative Solver Approaches

Philipp von Manteuffel, Benjamin Blankertz

Chair for Neurotechnology Technische Universität Berlin

Tree Search Constraint Programming

Open paper AskPDF arXiv

We present an optimized approach for finding minimal move sequences to solve Flood-It puzzles using A* search and compare it with approaches using SAT, Integer Programming, and Constraint Programming solvers. The performance of A* search is considerably improved by using an appropriate heuristic and sophisticated equivalences of game states to limit the search space. Each aspect is systematically evaluated, providing insights that generalize to other problems. By comparing the best variant of each approach, the A* search is the fastest in finding a minimal solution in about 75 % of the Flood-It instances tested. This result is in line with our expectation since A* specifically looks for a minimum solution. In contrast, the SAT-based approach is designed to solve the decision problem of whether a solution with a given length exists. An iterative search is required to determine a minimum solution length using a SAT-based approach. However, with increasing complexity, quantified by the minimum solution length, the SAT-based approach outperforms A*. We also compared the different approaches to the decision problem, where A* again performed best for the largest number of puzzles. Here, again, SAT supersedes A* for higher complexities, albeit with a lower crossing point.