What I Have Learned From All
These Solver Competitions
 Preparations– CSP and CLP(FD)– Global constraints– Table constraints– Action rules
 Programming techniques– Use global constraints– Use table constraints– Use specialized propagators– Use problem-specific labeling strategies
by Neng-Fa Zhou at WLP'09
 Conclusion

1Constraint Satisfaction Problems
 CSP– A set of variables V={V1,…,Vn}– Each variable has a domain Vi :: Di– A set of constraints

 Example• A:{0,1}, B:{0,1}, C:{0,1}• C = A and B

 Solution to CSP– An assignment of values to the variables that satisfies
all the constraints
by Neng-Fa Zhou at WLP'09

2

CLP(FD)
 CLP(FD) language– An extension of Prolog that provides built-ins
for describing and solving CSPs
 CLP(FD) systems– B-Prolog, CHIP, ECLiPSe, GNU-Prolog,IF/Prolog, Prolog-IV, SICStus, SWI-Prolog,
YAP, …

by Neng-Fa Zhou at WLP'09

3

CLP(FD) - B-Prolog Domain constraints• X in D• X notin D Unification and arithmetic constraints• Exp R Exp– R is one of the following: #=, #¥=, #>, #>=, #<, #=– Exp may contain +, -, *, /, //, mod, sum, min, max Boolean constraints– Exp R Exp• R is one of the following: #/¥, #¥/, #=>, #<=>, #¥ Global constraints
 Labeling built-insby Neng-Fa Zhou at WLP'09

4

Example
X1

X2

X3

X4

X5

X7

X8

X6
X9 X10

X11 X12 X13 X14
X15 X16

go:Vars=[X1,X2,…,X16],
Vars :: 1..9,word([X1,X2],5),word([X3,X4,X5,X6],17),…
word([X10,X14],3),
labeling(Vars),
writeln(Vars).
word(L,Sum):sum(L) #= Sum,
all_different(L).

A Kakuro puzzle
by Neng-Fa Zhou at WLP'09

5

Global Constraints
 all_different(L) all_distinct(L) circuit(L) cumulative(Starts,Durations,Resources,Limit)

by Neng-Fa Zhou at WLP'09

6all_different(L) and
all_distinct(L) all_different(L)– Let L=[X1,…,Xn].
For each i,j∈1..n (i<j) Xi ≠ Xj.
 all_distinct(L)– Maintains some sort of hyper-arc consistency• Hall-set finding (B-Prolog and ECLiPSe)• Regin’s Maximum-matching (SICStus)by Neng-Fa Zhou at WLP'09

7

circuit(L) Let L=[X1,…,Xn], where Xi ∈1..n. An assignment(X1/a1,…,Xn/an)
satisfies this constraint if{1→ a1 ,…,n→ an}forms a Hamiltonian cycle.
 Propagation algorithms– Remove non-Hamiltonian arcs as early as
possible• Avoid sub-cycles– Reachability test
by Neng-Fa Zhou at WLP'09

8cumulative(Starts,Durations,Resources,Limit) Starts=[S1,…,Sn],Durations =[D1,…,Dn],Resources =[R1,…,Rn],
The resource limit cannot be exceeded at any time When Resources=[1,…,1] and Limit=1⇓
serialized(Starts,Durations)– Disjunctive scheduling• Edge-finding algorithms are usedby Neng-Fa Zhou at WLP'09

9

Table Constraints
 Positive constraints(X,Y,Z) in [(0,1,1),(1,0,1),(1,1,0)] Negative constraints(X,Y,Z) notin [(0,1,1),(1,0,1),(1,1,0)]by Neng-Fa Zhou at WLP'09

10

Action Rules
Agent, Condition, {EventSet} => Action

 Events– Instantiation: ins(X)– Domain• bound(X), dom(X), dom(X,E), dom_any(X), anddom_any(X,E)– Time : time(X)– GUI• actionPerformed(X), mouseClicked(X,E)…

– General• event(X,O)
by Neng-Fa Zhou at WLP'09

11

Applications of Action Rules Lazy evaluation
freeze(X,G), var(X), {ins(X)} => true.
freeze(X,G) => call(G).

 Constraint propagators'X in C-Y_ac'(X,Y,C),var(X),var(Y),{dom(Y,Ey)}=>
Ex is C-Ey,exclude(X,Ex).
'X in C-Y_ac'(X,Y,C) => true.
by Neng-Fa Zhou at WLP'09

12

Use Global Constraints
all_distinct(L) (1) Graph coloring– Model-1 (neq)• For each two neighbors i and j, Ci≠Cj– Model-2 (all_distinct)• For each complete subgraph {i1,i2,…,ik},
all_distinct([Ci1, Ci2,…, Cik])• post_neqs(Neqs) in B-Prolog

by Neng-Fa Zhou at WLP'09

13

Use Global Constraints
all_distinct(L) (2) Benchmarking results (seconds)

Source of benchmarks:
Agostino Dovier, Andrea Formisano, and Enrico Pontelli,
A comparison of CLP(FD) and ASP solutions to NP-complete problems,
ICLP’05.
by Neng-Fa Zhou at WLP'09

14

Use Global Constraints
all_distinct(L) (3) N-Queens problem  Model-1 (neq)– For i,j∈1..n (i < j)Qi ≠ Qj

Qi-Qj ≠ (j-i)

Qj-Qi ≠ (j-i)

 Model-2 (all_distinct)– all_distinct([Q1,…,Qn]),
all_distinct([Q1,Q2-1,…,Qn-n]),all_distinct([Q1,Q2+1,…,Qn+n])

by Neng-Fa Zhou at WLP'09

15

Use Global Constraints
all_distinct(L) (4) Benchmarking results (ms)Source of benchmarks:
2nd ASP Competition

by Neng-Fa Zhou at WLP'09

16Use Global Constraints
all_distinct(L) (5) Some times all_different(L) is faster than

all_distinct(L) An example: Golomb ruler
M1 M2

M3 M4
all_different([M2-M1,M3-M1,M4-M1,M3-M2,M4-M2,M4-M3])

by Neng-Fa Zhou at WLP'09

17

Use Global Constraints
all_distinct(L) (6) Benchmarking results (seconds)

Source of benchmarks: 2nd ASP Competition
by Neng-Fa Zhou at WLP'09

18

Use Global Constraints
circuit(L) The Traveling Salesperson Problem
tsp(Vars):Vars=[V1,V2,…,V8],
V1 :: [2,3,4],
V2 :: [1,3,6,7],…
V8 :: [5,6,7],circuit(Vars).

by Neng-Fa Zhou at WLP'09

19

Use Global Constraints
serialized(Starts,Durations) (1) Scheduling– Model-1: use disjunctive constraints
VV5+97#=<VV17#¥/VV17+52#=<VV5,
VV5+97#=<VV26#¥/VV26+59#=<VV5,
VV5+97#=<VV32#¥/VV32+41#=<VV5,
VV5+97#=<VV49#¥/VV49+63#=<VV5,…..
– Model-2: use global constraints• post_disjunctive_tasks(Disjs) in B-Prolog
Disjs=[disj_tasks(S1,D1,S2,D2),…]– converts disjunctive constraints into serialized
by Neng-Fa Zhou at WLP'09

20

Use Global Constraints
serialized(Starts,Durations) (2) Benchmarking results

Source of benchmarks:
www.cril.univ-artois.fr/~lecoutre/research/benchmarks/benchmarks.html
by Neng-Fa Zhou at WLP'09

21

Use Table Constraints (1) The Schur number problem– Partition n positive integers into m sets such that all of
the sets are sum-free.

 Model-1 (sum-free triplet)
Si = Sj → Si+j ≠ Si

 Mode-2 (use redundant constraints)
Si=Sj → Si+j≠Si, Si=Si+j → Sj≠Si, Sj=Si+j → Si≠Sj.

 Mode-3 (use table constraints)(Si,Sj,Si+j) notin [(1,1,1),(2,2,2),…]by Neng-Fa Zhou at WLP'09

22

Use Table Constraints (2)The Schur number problem
 Benchmarking results (seconds)

Source of benchmarks: 2nd ASP Competition
by Neng-Fa Zhou at WLP'09

23

Use Table Constraints (3)The Knights Problem
 Model-1: use disjunctive constraints(abs(P1//N-P2//N)#=1 #/¥ abs(P1 mod N-P2 mod N)#=2) #¥/(abs(P1//N-P2//N)#=2 #/¥ abs(P1 mod N-P2 mod N)#=1)

 Model-2: use table constraints(P1,P2) in [(0,6),(0,9),(1,7),(1,8),(1,10),…]by Neng-Fa Zhou at WLP'09

24

Use Table Constraints (4)The Knights Problem
 Benchmarking results (seconds)

Source of benchmarks:
www.cril.univ-artois.fr/~lecoutre/research/benchmarks/benchmarks.html
by Neng-Fa Zhou at WLP'09

25

Don’t Use Table Constraints
 The Black Hole problem(X,Y) notin [(0,0),(1,1),(2,2),…]

 Transform table constraints(X,Y) notin [(0,0),(1,1),(2,2),…],↓X #¥= Y↓
all_distinct(…)

by Neng-Fa Zhou at WLP'09

26

Don’t Use Table Constraints
The Black Hole problem
 Benchmarking results (seconds)

www.cril.univ-artois.fr/~lecoutre/research/benchmarks/benchmarks.html
by Neng-Fa Zhou at WLP'09

27

Use Specialized
Propagators(1) Example 1: abs(X-Y)#=N
fd_abs_diff_ins(X,Y,N),var(X),{ins(X)} => true.
fd_abs_diff_ins(X,Y,N) =>Ey1 is X-N,
Ey2 is X+N,
Y in [Ey1,Ey2].
fd_abs_diff_dom(X,Y,N),var(X),var(Y),{dom_any(X,Ex)}=>
Ey1 is Ex-N, Ex1 is Ey1-N,(fd_false(X,Ex1)->fd_set_false(Y,Ey1);true),Ey2 is Ex+N, Ex2 is Ey2+N,(fd_false(X,Ex2)->fd_set_false(Y,Ey2);true).
by Neng-Fa Zhou at WLP'09

28

Use Specialized
Propagators(2) Model-4 (The Schur Number Problem )not_the_same(X,Y,Z),n_vars_gt(3,1),{ins(X),ins(Y),ins(Z)}=>true.
not_the_same(X,Y,Z),X==Y => fd_set_false(Z,X).
not_the_same(X,Y,Z),X==Z => fd_set_false(Y,X).
not_the_same(X,Y,Z),Y==Z => fd_set_false(X,Y).
not_the_same(X,Y,Z) => true.

by Neng-Fa Zhou at WLP'09

29

Use SpecializedPropagators(3) Benchmarking results (seconds)

Source of benchmarks: 2nd ASP Competition
by Neng-Fa Zhou at WLP'09

30

Use Problem-SpecificLabeling Strategies
 Variable selection– queens: labeling([ff],Vars)– golomb: labeling([],Vars)
 Value selection– tsp: select an edge with the lowest weightby Neng-Fa Zhou at WLP'09

31

Value Selection
 Select an edge with the lowest weighttsp(Vars):Vars=[V1,V2,…,V8],
V1 :: [2,3,4],
put_attr_no_hook(V1,nbs,[3,2,4]),V2 :: [1,3,6,7],
put_attr_no_hook(V2,nbs,[3,1,6,7]),…
V8 :: [5,6,7],
pub_attr_no_book(V8,nbs,[6,7,5]),
circuit(Vars).
Use get_attr(V,nbs,Nbs),member(V,Nbs)
rather than indomain(V) to label V.
by Neng-Fa Zhou at WLP'09

32

Conclusion
 Techniques– Use global constraints– Use table constraints– Use specialized propagators– Use problem-specific labeling strategies More techniques and systems to explore– Integrating CLP(FD) with SAT and ASP solvers
 Thanks!
– Organizers of the solver competitions– Program committee of WLP’09
by Neng-Fa Zhou at WLP'09

33