Everything about Constraint programming
Computer programming paradigm
Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state the constraints on the feasible solutions for a set of decision variables. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. In addition to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronological backtracking and constraint propagation, but may use customized code like a problem-specific branching heuristic. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Constraint programmingA 5-minute orientation
- Skim a recent paper: Safety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite ProgrammingInfluential work since 2022
- Pick up a classic book: Trends in constraint programmingThe most-reprinted book on the subject
- Read the landmark paper: Chance-Constrained ProgrammingCited 2,151 times
- Go sideways: Constraint satisfactionA closely related topic
- Go sideways: Constraint satisfaction problemA closely related topic
📖 Definitions
Noun A declarative paradigm for modeling and solving satisfaction and optimization problems through variables with specified domains and relational constraints, separating the specification of admissible assignments from the procedures used to compute them.
🏆 Landmark papers (most cited)
Chance-Constrained Programming
Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure
Constraint logic programming: a survey
Constraint logic programming languages
Constraint satisfaction using constraint logic programming
Sets and constraint logic programming
Constrained clustering by constraint programming
🆕 Influential since 2022
Safety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite Programming
Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook
Choco-solver: A Java library for constraint programming
Industrial-size job shop scheduling with constraint programming
Network configuration distributed production scheduling problem: A constraint programming approach
📚 Books worth reading
Trends in constraint programmingFrédéric Benhamou, Narendra Jussien · 2007- 📕Ant colony optimization and constraint programmingChristine Solnon · 2010
Constraint networksChristophe Lecoutre · 2009
Constraint logic programming using ECLiPSeKrzysztof R. Apt, Mark Wallace · 2006
Tree-based graph partitioning constraintXavier Lorca · 2011- 📕Abstract Domains in Constraint ProgrammingMarie Pelleau · 2014
- 📕Algorithms and Ordering Heuristics for Distributed Constraint Satisfaction ProblemsMohamed Wahbi · 2013
The logical thinking processH. William Dettmer · 2007
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Constraint satisfaction In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose…
- Constraint satisfaction problem Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations…
- Constraint logic programming Constraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction…
- Local consistency In constraint satisfaction, local consistency conditions are properties of constraint satisfaction problems related to the consistency of subsets of variables…
- Look-ahead (backtracking) In backtracking algorithms, look ahead is the generic term for a subprocedure that attempts to foresee the effects of choosing a branching variable to…
- Complexity of constraint satisfaction The complexity of constraint satisfaction is the application of computational complexity theory to constraint satisfaction. It has mainly been studied…
- Hybrid algorithm (constraint satisfaction) Within artificial intelligence and operations research for constraint satisfaction a hybrid algorithm solves a constraint satisfaction problem by the combinatio…
- Backtracking Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction or enumeration problems, that…