Constraint Logic Programming

Origin. Jaffar and Lassez introduced CLP scheme (1987). Extends logic programming with constraint solving. Combines Prolog-style reasoning with domain-specific solvers. Foundation for constraint satisfaction and optimization. Systems: CLP(R), CLP(FD), ECLiPSe, SICStus.

Models. Logic programming with constraints. Prolog: unification only. CLP: add domain constraints (arithmetic, finite domains, etc.). Goals include constraints; solver maintains consistency. Combines declarative logic with efficient specialized solvers.

Formalism.

CLP(X) scheme: X: constraint domain (R, Q, FD, etc.)

Syntax: Clauses: H :- B₁, ..., Bₙ, c₁, ..., cₘ where Bᵢ are atoms, cⱼ are constraints.

Constraint domains:

CLP(R): real arithmetic (X > 0, X + Y = Z)
CLP(Q): rational arithmetic
CLP(FD): finite domains (X in 1..10, all_different)
CLP(B): Boolean constraints

Execution: Maintain constraint store. Add constraints, check satisfiability. Backtrack if store becomes unsatisfiable.

Example (CLP(FD)): sudoku(Rows) :- append(Rows, Vs), Vs ins 1..9, maplist(all_distinct, Rows), transpose(Rows, Cols), maplist(all_distinct, Cols), blocks(Rows), label(Vs).

Propagation: Constraints propagate: X in 1..9, X > 5 → X in 6..9. Reduces search space.

Labeling: Enumerate solutions after propagation. Search strategies: first-fail, etc.

Symbols.

Symbol	Unicode	Name	Meaning
:-	—	Rule	If
ins	—	In set	Domain
#=	—	Constraint equals	Arithmetic
#<	—	Constraint less	Inequality
all_different	—	All distinct	Global constraint
label	—	Label	Enumerate

Metatheory. CLP sound and complete for constraint domain. Constraint solving: domain-specific algorithms. Propagation: incomplete but efficient. Search: complete enumeration. Complexity: NP-complete for FD, polynomial for some continuous.

Applies to. Scheduling. Planning. Configuration. Rostering. Puzzle solving. Optimization. Bioinformatics. Hardware verification.

Limitations. Efficiency depends on propagation. Global constraints domain-specific. Scaling to large problems. Learning curve for constraints. Debugging constraint programs. Floating-point issues for CLP(R).