A first look at Answer Set Programming
Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers -- programs for generating stable models are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates (unlike Prolog query evaluation, which may lead to an infinite loop).In 2001 I first read about Answer Set Programming as a byproduct from an interest in planning and automated theorem proving. I then implemented the ASP program who_killed_agatha.lp, but didn't pursue this interest much more. After that I have - in different times - been very fascinated by this paradigm, especially how succint and clear many of these programs are.
The last weeks I did a more systematic take on ASP and have implemented about 50 different ASP programs (see my Answer Set Programming Page), among them many of the learning problems I use as a stepping stone when learning a new CP system. A full list of the implemented programs and problem instances is shown below.
Answer Set Programming is a huge subject and I will barely scratch the surface here. The object of this blog post is to show how some standard CP problems (and not so standard problems) can be implemented in ASP. I realize that having this approach don't show off some very nice features/applications of ASP, such as the connection to planning, database query, etc. See this as ground for future projects. Also, I have been more concerned about understand how to program in ASP than finding the best heuristics (solver parameters) for each problem. That said, there are some benchmark comparisons below which may not be representative for what ASP systems can do.
My system
All programs was run on this computer: Linux Ubuntu 10.4, 64-bit with 8 cores (Intel i7 930, 2.80GHz) and 12 Gb RAM.Grounders and solvers
The ASP systems I have worked with solves a problem in two steps. Given a file in apropriate format:- first a grounder "grounds" the problem file(s) to an intermittent format. In principle this means that all possible values of the variables are generated including all the combinations that are forbidden by integrity constraints. Note: This can be very large files.
- then a solver reads this grounded file and - hopefully - solves the problem by generating answers sets (solutions).
Another option was to use the grounder/solver lparse/smodels but I decided to use Potassco since it seems to be much more active and it include a lot of other tools, for example clingcon (using constraint programming domains etc), which I will study more later.
Another reason to use the Potassco tools was the impressive results in The Second Answer Set Programming Competition (for year 2010). For more about this, see the report The Second Answer Set Programming Competition (PDF).
However, with some few problem I also compared with with lparse/smodels, e.g. send_more_money.lp.
Note that I have not tweaked very much with the large amount of flags for the clasp solver. In some problems (e.g. the alphanumeric) I tested some of them but didn't find any that speeded it up considerably.
More information about ASP
Here are some useful links for Answer Set Programming:- Wikipedia Answer_set_programming
- The First Answer Set Programming System Competition
- The Second Answer Set Programming Competition
- Third Answer Set Programming Competition - 2011
- Asparagus
- Benchmarks
- Texas Action Group (TAG, TAG Members). TAG technical discussions.
- Thomas Eiter, Giovambattista Ianni, Thomas Krennwallner: Answer Set Programming: A Primer (PDF)
- The book Knowledge Representation, Reasoning and Declarative Problem Solving by Chitta Baral (2003, Cambridge University Press, ISBN: 9780521147750). I started to read it some days ago and it seems to be very interesting. It's quite theoretical but also contains a lot of encoding examples.
ASP Systems
There are many ASP systems. Here are those I have tested most.- Lparse/Smodels.
- Potassco Answer Set Solving Collection, includes clasp, Gringo, Clingo, and other tools. These are the systems I tend to use. Also see Potasssco Labs.
- DLV. DLV is a combined grounder/solver and has some interesting features and extensions. The syntax is not very different from Lparse but I have not tried to make my ASP programs work with DLV.
Some programs
Here is some examples how one can encode some problems with ASP (or rather in lparse/gringo format). Let's start with Sudoku.Sudoku
Program: sudoku.lpHere is one encoding of the problem (inspired by this). The hints part is described below.
% domains val(1..9). border(1;4;7). % alldifferent rows, columns, values 1 { x(X,Y,N) : val(N) } 1 :- val(X;Y). 1 { x(X,Y,N) : val(X) } 1 :- val(N;Y). 1 { x(X,Y,N) : val(Y) } 1 :- val(N;X). % alldifferent: boxes 1 { x(X,Y,N) : val(X;Y): X1<=X:X<=X1+2:Y1<=Y:Y<=Y1+2 } 1 :- val(N), border(X1;Y1).One really big difference with coding ASP and CP is that in CP the data is often in matrix/array form (except maybe for the Prolog based CP systems). In ASP there are no arrays or matrices, so instead one have to state the order and "coordinates" by enumerating the combinations. E.g. the following problem instance is normally coded in CP as something like (where "_" must replaced with "0" in some systems).
_,_,6, _,_,_, _,9,_, _,_,_, 5,_,1, 7,_,_, 2,_,_, 9,_,_, 3,_,_, _,7,_, _,3,_, _,5,_, _,2,_, _,9,_, _,6,_, _,4,_, _,8,_, _,2,_, _,_,1, _,_,3, _,_,4, _,_,5, 2,_,7, _,_,_, _,3,_, _,_,_, 8,_,_In ASP encodings this is stated as predicates
x(Row, Column, Value)
, e.g.:
x(1, 3, 6). x(1, 8, 9). x(2, 4, 5). x(2, 6, 1). ... x(8, 6, 7). x(9, 2, 3). x(9, 7, 8).This lack of direct matrix representation (and no direct representation of arrays) has been one of the biggest hurdle when translating the MiniZinc models to ASP. (It takes a lot of time to manually convert the matrix representation to this predicate variant, so I've created a simple Perl program for this: matrix2predicate.pl)
OK, now some explanations of the ASP encoding above.
val
and border
is "domain predicates" which contains the
different values (1..9, and 1,4,7 respectively) to use in the program. They are
used to generate different values later on.
Next we have the constraints that all rows, columns, and boxes should contain different values. In Constraint Programming this is (normally) done with a bunch of
alldifferent
constraints, but in ASP we (normally) have to use another approach.
(however there are some systems, e.g. clingcon mentioned above, that is a hybrid
of ASP and CP which includes some global constraints.)
Instead one have to use some other features which can be described as.
- "generators"
- cardinality constraint
- integrity constraint
1 { x(X,Y,N) : val(N) } 1 :- val(X;Y).
is to ensure that the indices in the "matrix" (X
and Y
) are unique, i.e. that the we have exactly 1 occurrence of x(1,1,Val)
(for some value Val), 1 occurence of x(1,2, Val)
etc.
The left "1" around the curly braces is the lower bound, and the right "1" is the upper bound of the expression. This is the cardinality constraints (think
atleast
and atmost
in CP). The part after the colon (:) - : val(N)
- is a condition filter which
here means that N
must take the values of the domain val/1
(i.e. the values 1..9).
The right part (the body)
val(X;Y)
is used as a "generator" of the expression; I tend to think of this as a "for loop" over X and Y that "drives" the left part.
Continuing with the next two lines:
1 { x(X,Y,N) : val(X) } 1 :- val(N;Y).
1 { x(X,Y,N) : val(Y) } 1 :- val(N;X).
These act as alldifferent constraints: for each combination of val(N) and val(Y) (
val(X;Y)
is a shorthand for val(X)
and val(Y)
) there must be exactly one occurrence of X
(the rows). And the next line is for Y.
The last constraint
1 { x(X,Y,N) : val(X;Y): X1<=X:X<=X1+2:Y1<=Y:Y<=Y1+2 } 1 :- val(N), border(X1;Y1).is for the boxes, and we can here see how the filter conditions (the ":" parts) can be combined. Note that the "loop" is over
X1
and Y1
.
Note: There is an alternative version of the constraints for the rows, columns, values which seems to be slighly faster:
% alternative: :- 2 { x(X,Y,N) : val(N) }, val(X;Y). :- 2 { x(X,Y,N) : val(X) }, val(N;Y). :- 2 { x(X,Y,N) : val(Y) }, val(N;X).These "headless" expressions (starts with
:-
) are integrity constraints which are used to remove certain results: if the expression is true then it don't belong to a solution. They all states that the occurrences of each value (X;Y) cannot be 2 or larger.
nqueens
Program: nqueens.lpLet's continue with another standard CP problems and compare the performances between encoding in ASP and some CP systems. Here is a complete encoding for n-queens problem in ASP: nqueens.lp.
#const n = 8. number(1..n). % alldifferent 1 { q(X,Y) : number(Y) } 1 :- number(X). 1 { q(X,Y) : number(X) } 1 :- number(Y). % remove conflicting answers :- number(X1;X2;Y1;Y2), q(X1,Y1), q(X2,Y2), X1 < X2, Y1 == Y2. :- number(X1;X2;Y1;Y2), q(X1,Y1), q(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2. :- number(X1;X2;Y1;Y2), q(X1,Y1), q(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.The first line (
#const n = 8.
) is a constant, and can be redefined
from the command line with different grounders/solvers:
$ clingo -c n=12 nqueens.lp $ gringo -c n=12 nqueens.lp | clasp $ lparse -c n=12 nqueens.lp | smodels $ lparse -c n=12 nqueens.lp | claspThe program use the same principles as for the Sudoku encoding. We represent the queens as a predicate
q(X, Y)
where X
is the position
in the "array" q
, and Y
is the value. (Or maybe as a
2-dimensional matrix of row X and column Y, but I tend to think about arrays with
a unique index.)
% alldifferent 1 { q(X,Y) : number(Y) } 1 :- number(X). 1 { q(X,Y) : number(X) } 1 :- number(Y).The first line ensures unicity of the
X
:s, and the second line
ensure the unicity of the Y
:s.
After that is the constraints (and integrity constraints) stating that the queens can not be placed on the same line, same row or column.
Since it is a standard benchmark problem in CP, I thought it might be interesting to see how well this ASP program do.
Below are some statistics for generating the first solution for different values of
n
, with two different grounders (gringo and lparse)
and two solvers (clasp and smodels). I had a tiny time limit
for these problems, 2 minutes (except for N=200). Here smodels didn't
do very well so I skipped it for N larger than 50.
In this table the times for the grounders and the solvers are separared. As we can see there is quite a difference of the times for the two grounders (gringo, lparse) and the solvers (clasp, smodels).
N Grounder Time Solver Time Choices Conflicts Restarts ---------------------------------------------------------------- 8 gringo 0.006s clasp 0.004s 5 2 0 8 gringo 0.006s smodels 0.008s 5 - - 8 lparse 0.023s clasp 0.02s 4 1 0 8 lparse 0.023s smodels 0.02s 3 - - 50 gringo 1.14s clasp 0.424s 366 252 2 50 gringo 1.14s smodels > 2min - - - 50 lparse 3.34s clasp 0.37s 211 137 1 50 lparse 3.34s smodels > 2min - - - 100 gringo 15.5s clasp 3.81s 839 505 3 100 lparse 33.1s clasp 3.4s 599 332 2 200! gringo 3:38min clasp 45.3s 9782 7747 9 200 lparse 6:30min clasp 38.5s 3669 2347 6Note: The results above was obtained by the following:
$ time gringo -c n=200 nqueens.lp > xxx $ time clasp xxxHowever, it seems that piping the results directly to the solver is faster. The following
$ time gringo -c n=200 nqueens.lp | clasp
takes less time than running the programs separately: 4:01 minutes
(compare with 3:38min + 45s = 4.23min).
Using lparse,
$ time lparse -c n=200 nqueens.lp | clasp
: 6:28min
(compare with 6:30min + 38.5s = 7:08min).
Compare these numbers with the MiniZinc model using the same modelling approach: queens.mzn with Gecode/fz as solver. These times are much better except maybe for small N. Or rather, the ASP solvers seems to be quite competitive, it is the ASP grounders that take long time. MiniZinc uses the same principle: first the MiniZinc model is converted to a FlatZinc file, and then the CP solvers works on the FlatZinc file. The times below includes both these steps.
N Time Failures ------------------ 8 0.08s 3 50 0.2s 2 100 0.5s 60 200 2.9s 8 500 21.0s 25 1000 1:44min 0With the Google CP Solver program nqueens2.py (Python interface) we have even better results (for larger N times also without output):
N Time Failures Time without output ----------------------------------- 8 0.04s 3 50 0.08s 16 100 0.2s 12 0.1s 200 0.6s 1 0.5s 500 4.0s 25 2.9s 1000 16.1s 0 12.1sClingcon
As mentioned above, there is a hybrid of ASP and CP (clingcon which seems to be much faster. However, the example of n-queens in the distribution (queens.lp) don't give correct result. For n=8 it should be 92 solutions, but it generates 1066 solutions. There is an
alldifferent
predicate
in the program but it is commented which probably is the cause of this; removing
the comment generates a segmentation fault.
magic square
Program: magic_square.lpMagic squares is another standard CP problem.
#const n = 3. % the size #const s = n*(n*n + 1) / 2. % the num % domains size(1..n). val(1..n*n). % unique index of x 1 { x(Row, Col, N) : val(N) } 1 :- size(Row;Col). % alldifferent values of x 1 { x(Row, Col, N) : size(Row;Col) } 1 :- val(N). % sum rows :- not s #sum[ x(Row, Col, Val) : size(Col) : val(Val) = Val ] s, size(Row). % sum columns :- not s #sum[ x(Row, Col, Val) : size(Row) : val(Val) = Val ] s, size(Col). % Sum diagonals 1 and 2 :- not s #sum[ x(I, I, Val) : size(I) : val(Val) = Val ] s. :- not s #sum[ x(I, n-I+1, Val) : size(I) : val(Val) = Val ] s. #hide. #show x(Row, Col, N).Note here how the constraints of sums are encoded. We use an integrity constraint
:- not s #sum[ x(Row, Col, Val) : size(Col) : val(Val) = Val ] s, size(Row).
stating that if the sum is not s
, then it should be
removed. This is kind of awkward sometimes but it is often required.
Here are some statistics for 1 solution of different n:s. Running with
>
$ time gringo -c n=N magic_square.lp | clasp --stat
N gringo clasp Choices Conflicts Restarts -------------------------------------------------- 3 0.004s 0.009s 244 230 1 4 0.007s 0.041s 1764 1545 5 5 0.011s 0.061s 1946 1618 5 6 0.014s 8.509s 184347 172478 16 7 0.035s 6.007s 78131 72744 14 8 0.042s 1:56min 925330 858613 20 9 0.046s 2:32:37h 36674602 32898767 29In contrast to the n-queens problem the grounding step is quite fast, it is the solver step that takes time. This also means that it may be room for a lot of improvements via different parameter settings of clasp.
Compare this with MiniZinc model (magic_square.mzn) that use about the same approach using Gecode/fz as the solver:
N time failures ------------------ 3 0.077s 3 4 0.076s 7 5 0.077s 678 6 0.083s 810 7 14:52m 99401166Here the gringo/clasp implementation manage to handle larger N than the MiniZinc+Gecode/fz approach. However the plain Gecode version (magic-square) using standard settings is faster on some of the problem instances. It's quite interesting that the ASP program is faster than Gecode for N=8 (and assuminly also for N=9).
N time failures ------------------ 3 0.008s 6 4 0.013s 892 5 0.427s 72227 6 0.009s 27 7 2.628s 481301 8 > 1hourNote: the Gecode mode has some symmetry breaking:
x(1,1) > x(1,n)
and x(1,1) > x(n,1)
. When I tried these in the ASP program it seems to be slower, not faster.
At last the mandatory declaimer: It's perhaps misleading to compare times on different systems/approaches like this. But it might give a good feeling of these systems/models.
Papers on Comparisons ASP vs CP
There have been some more systematic comparisons of ASP and CP, which - as I understand - is written by ASP researchers:- Agostino Dovier, Andrea Formisano, Enrico Pontelli: An Empirical Study of Constraint Logic Programming and Answer Set Programming Solutions of Combinatorial Problems. Comparing ASP (smodels, cmodels) and CLP(FD) (SICStus Prolog, GNU Prolog) on different problems: Coloring, Hamilton, Schur, Protein Structure Prediction, Planning, Knapsack, Binary codes.
- Mehmet Celik, Halit Erdogan, Fırat Tahaoglu, Tansel Uras, Esra Erdem: Comparing ASP and CP on Four Grid Puzzles: Compares clasp and Comet on four grid puzzles: Akari, Kakuro, Nurikabe, and Heyawake.
Other programs
Here is another samples of ASP programs together with some code and comments.Who killed Agatha
Program: who_killed_agatha.lp As mentioned above, this was actually my first program in ASP, written when I first read about ASP, about 2002. (And that's why this problem has been a standard problem since.)Here we see more of the declarative aspect of ASP and its use of defined predicates (
hates/2
, richer/2
) which are then used in integrity constraints.
% "Someone who lives in Dreadsbury Mansion, killed aunt Agatha. Agatha, % the butler, and Charles live in Dreadsbury Mansion, and are the only % people who live therein." % The people in this drama person(agatha;butler;charles). % Exactly one person killed agatha 1 {killed(agatha,agatha), killed(butler,agatha), killed(charles,agatha)} 1. % A killer always hates her victim, and is never richer than her victim hates(Killer,Victim) :- person(Killer), person(Victim), killed(Killer,Victim). :- richer(Killer,Victim), person(Killer), person(Victim), killed(Killer,Victim). % a person cannot be richer than him/herself richer(X,Y) :- person(X), person(Y), X != Y. % Charles hates no one that aunt Agatha hates 0 { hates(charles,X) } 0 :- person(X), hates(agatha,X). % Agatha hates everyone except the butler, ... hates(agatha,X) :- person(X), X != butler. % ... and no one the butler does not hate. :- hates(agatha,X), person(X), hates(butler,X). % the butler hates everyone not richer than aunt Agatha :- hates(butler, X), person(X), richer(X,agatha). % No one [in Dreadsbury Mansion] hates everyone {hates(X,Y):person(Y)} 2 :- person(X). % Who killed aunt Agatha? {killed(X,agatha):person(X)}. #hide. #show killed(X,Y).
Diet
Program: diet1.lpThis is a simple optmization problem where the object is to minimize the cost of the products given that we must exceed some limits of the ingredients
#const n = 10. amount(0..n). % max amount of each product % food calories chocolate sugar fat price % (ounces) (ounces) (ounces) (ounces) food_a(chocolate_cake, 400, 3, 2, 2, 50). food_a(chocolate_ice_cream, 200, 2, 2, 4, 20). food_a(cola, 150, 0, 4, 1, 30). food_a(pineapple_cheesecake, 500, 0, 4, 5, 80). % Minimum limits limits(calories, 500). limits(chocolate, 6). limits(sugar, 10). limits(fat, 8). % extract the different nutrition types calories(Food, Amount) :- food_a(Food, Amount, _, _, _, _). chocolate(Food, Amount) :- food_a(Food, _, Amount, _, _, _). sugar(Food, Amount) :- food_a(Food, _, _, Amount, _, _). fat(Food, Amount) :- food_a(Food, _, _, _, Amount, _). % extrace the price price(Food, Price) :- food_a(Food, _, _, _, _, Price). prices(Price) :- price(Food, Price). % food(chocolate_cake;chocolate_ice_cream;cola;pineapple_cheesecake). food(F) :- food_a(F, _,_, _, _, _). % each food has exactly one Price and one Amount 1 { food_price_amount(Food,Price,Amount) : amount(Amount) } 1 :- food(Food), price(Food, Price). :- #sum[food_price_amount(F, _, A) : calories(F, C) = C*A] L-1, limits(calories, L). :- #sum[food_price_amount(F, _, A) : chocolate(F, C) = C*A] L-1, limits(chocolate, L). :- #sum[food_price_amount(F, _, A) : sugar(F, C) = C*A] L-1, limits(sugar, L). :- #sum[food_price_amount(F, _, A) : fat(F, C) = C*A] L-1, limits(fat, L). #minimize [food_price_amount(F,Price,Amount) = Price*Amount ].The way I have encoded it is rather complex but most of it is to extract different values from the predicate
food_a
. I have
a feeling that there is a much better way...
A comment on the
#sum
construct. This code
:- #sum[food_price_amount(F, _, A) : calories(F, C) = C*A] L-1, limits(calories, L).means that the sum of the products of the amount of food (
A
) and the calories
in the food (C
) should be larger than the limit (L
) of this
food. Since it's a integrity constrain we must negate the expression.
The objective is to minimize (
#minimize
) the cost of all selected products.
For me this problem is easier to encode with a traditional "array/matrix" approach in CP, and it is also easier to generalize (by just adding a dimension or two to the arrays). Compare for example with the MiniZinc model diet1.mzn
However, I like that it is possible to use symbolic domains directly instead of using integers (and enums).
SEND+MORE=MONEY and other alphametic problems
Program: send_more_money.lpProgram: send_more_money_any_base.lp
Program: send_most_money.lp
Program: least_diff.lp
Here is my encoding of SEND+MORE=MONEY (send_more_money.lp). Note the use of the domain predicate
letter)
to define the "slots" in the "array" x(Letter, Value
which are then extracted in the main predicate smm
. Also note that we have to use :- not smm
in order to remove the combinations we don't want (i.e. remove everything that is not satified by the rules in smm
).
letter(s;e;n;d;m;o;r;y). values(0..9). % exact 1 occurrence of each letter 1 { x(L,Val) : values(Val) } 1 :- letter(L). % 0..1 occurrences of each value { x(L,Val) : letter(L) } 1 :- values(Val). % no digit can be given to two different symbols % :- letter(L), letter(L1), x(L,V1), x(L1,V1), L != L1. smm :- values(S;E;N;D;M;O;R;Y), x(s,S), x(e,E), x(n,N), x(d,D), x(m,M), x(o,O), x(r,R), x(y,Y), M > 0, S > 0, S*1000+E*100+N*10+D + M*1000+O*100+R*10+E == M*10000+O*1000+N*100+E*10+Y. :- not smm.I was surprised - and somewhat disappointed - that it took so long to solve these kind of alphametic problems with standard ASP tools. It took about 45 seconds to solve this with clingo (gringo + clasp). lparse accept this encoding with just some warnings and it takes 25s.
After a while I realized that it is the grounding (gringo) that takes so long, almost all of the 45 seconds. Given this grounding as a file, then the solvers - clasp and smodel - solves this in no time, about 0.004s.
clingcon:
There is also an example of this problem in clingcon's distribution (sendmoremoney1.lp). It works and is very fast (0.001s). However, I have not fully understood how to encode other similar problems with optimizations, different domains, etc (e.g. SEND + MOST + MONEY) etc, so understanding this is a further project. Also, it seems to have some bugs in the current version, especially regarding global constraints.
send_most_money.lp
This solves the problem SEND+MOST=MONEY and maximizes MONEY. It seems to works since it show the correct maximum value of MONEY (10768). Almost, since the value of
Optimization
is not this value but a much larger number
(4949944124). I read in the Potassco documentation that maximization is converting
to minimization with the weights inversed. Maybe the weird Optimization value is a
consequence of that?
Answer: 1 x(e,6) x(n,7) x(d,3) x(m,1) x(o,0) x(t,5) x(y,8) x(s,9) y(money,10768) Optimization: 4949944232 Answer: 2 x(e,7) x(n,8) x(d,4) x(m,1) x(o,0) x(t,2) x(y,6) x(s,9) y(money,10876) Optimization: 4949944124 OPTIMUM FOUNDAs with send_more_money.pl it takes a long time to solve it: 2:24 minutes with clingo (gringo/clasp). With lparse/smodels it takes much longer.
gringo/clasp: 2:24 minutes
gringo/smodels: over 7 minutes and then some "strange" result is shown from
smodels (e.g. not y(money,98979)
) and I stopped.
lparse/smodels: over 10 minutes for lparse
lparse/clasp: over 10 minutes for lparse
send_more_money_any_base.lp: SEND+MORE=MONEY for "any" baseFor n=10 it takes the same time as for send_more_money.lp. For n=11 it takes 1:37 minutes to show all 3 solutions.
least_diff.lp
I have also implemented the least diff problem, but I stopped the program after 30 minutes without any answer.
Well, maybe my approach in these problems is not a good example of how to use ASP. However, they are standard examples in CP.
Other standard CP/OR problems
Here are some other standard CP or OR problems.all_interval.lp: All interval.
langford.lp: Langford numbers
This follows quite nicely the MiniZinc version in langford.mzn
#const k = 4. val(1..k). % for solution pos(1..2*k). % for position % alldifferent position 1 { position(I, N) : pos(N) } 1 :- pos(I). 1 { position(I, N) : pos(I) } 1 :- pos(N). % The difference in position between the two I's is I. :- position(I+k, N1), position(I, N2), N1 != N2 + I+1, val(I). % solution: unique index 1 { solution(I, N) : val(N) } 1 :- pos(I). % exactly two occurrences of 1..k 2 { solution(I, N) : pos(I) } 2 :- val(N). % channel solution <-> position :- position(I, P1), solution(P1, I2), I != I2, val(I;I2). :- position(I+k, P2), solution(P2, I2), I != I2, val(I;I2).alldifferent_except_0.lp: All different except 0
Since there is no concept of global constraints in ASP, one has to code these kind of constraints directly:
#const n = 6. #const m = 9. values(0..m). ix(1..n). % unique indices of x, 1..n 1 { x(I, Val) : values(Val) } 1 :- ix(I). % alldifferent except 0 % If Val > 0 then there must be 0..1 % occurrences of Val in x. { x(I, Val) : ix(I) } 1 :- values(Val), Val > 0. % Additional constraint: There must be exactly 2 zeros. % 2 #sum [ x(I, 0) : ix(I) = 1 ] 2. % Alternative: :- not 2 #sum [ x(I, 0) : ix(I) = 1 ] 2.bus_scheduling.lp: Simple scheduling problem
organize_day.lp: Another simple scheduling problem: How to organize a day
The no overlap requirement are done with the following. A task is defined as the predicate
task(TaskId, StartTime, EndTime)
. The predicate no_overlap
is very much Prolog, apart from that the order of rules and the order of predicates don't matter in ASP.
% No overlap of tasks no_overlap(Task1, Task2) :- task(Task1, Start1, End1), task(Task2, Start2, End2), End1 <= Start2. no_overlap(Task1, Task2) :- task(Task1, Start1, End1), task(Task2, Start2, End2), End2 <= Start1. :- tasks(Task1;Task2), Task1 != Task2, not no_overlap(Task1, Task2).photo.lp: Photo problem.
This is an example from Mozart/Oz tutorial on FD. The object is to maximize the number of satisfied preferences. I like this direct approach.
persons(betty;chris;donald;fred;gary;mary;paul). positions(1..7). % Preferences: pref(betty, gary;mary). pref(chris, betty;gary). pref(fred, mary;donald). pref(paul, fred;donald). % alldifferent positions 1 { position(Person, Pos) : positions(Pos) } 1 :- persons(Person). 1 { position(Person, Pos) : persons(Person) } 1 :- positions(Pos). next_to(P1,P2) :- pref(P1,P2), position(P1,Pos1), position(P2,Pos2), |Pos1-Pos2| == 1. % maximize the number of satisfied preferences #maximize [ next_to(P1,P2) ].post_office_problem2.lp: Post office problem
coloring.lp: Simple map coloring problem
countries(belgium;denmark;france;germany;netherlands;luxembourg). colors(red;green;blue;white). arc(france,belgium;luxembourg;germany). arc(luxembourg,germany;belgium). arc(netherlands,belgium). arc(germany,belgium;netherlands;denmark). neighbour(X,Y) :- arc(X,Y). neighbour(Y,X) :- arc(X,Y). 1 {color(X, C) : colors(C) } 1 :- countries(X). :- color(X1, C), color(X2, C), neighbour(X1,X2). :- color(germany, red).A variant to the generator line (line 9) is to explicit state the different alternative with disjunction using '|' (bar):
color(X, red) | color(X, green) | color(X, blue) | color(X, white) :- countries(X).However, then one has to use the parameter
--shift
to gringo/clingo for this to work.
xkcd.lp: xkcd problem
This is a subset sum (or knapsack depending on the definition) problem from xkcd. The object is to select dishes so they give a total of 15.05 (as 1505 in the encoding).
#const total = 1505. #const n = 10. amount(0..n). food(mixed_fruit;french_fries;side_salad;host_wings;mozzarella_sticks;samples_place). price(mixed_fruit,215). price(french_fries,275). price(side_salad,335). price(host_wings,355). price(mozzarella_sticks,420). price(samples_place,580). prices(P) :- price(_, P). % each food has exactly one amount 1 { food_amount(Food, Amount) : amount(Amount) } 1 :- food(Food). % sum to the exact amount total [ food_amount(F, Amount) : price(F, Price) : prices(Price) : amount(Amount) = Price*Amount ] total.One can easily change the total (e.g. to 1506) with
clingo -c total=1506 xkcd.lp
. Also, here is an (not uncommon) example that the data part is larger than the actual program.
subset_sum.lp: Another subset sum problem
3_jugs.lp: 3 jugs problem (as a graph problem)
Here is a graph approach to the 3 jugs problem which shows another use of an adjacency predicate (
adj
). Here we also add the edge visited with an index to get the order in the graph traversal. The graph is of the states of the different ways of pouring from the jugs. The object is to get the shortest path from node 1 to node 15. Note that we select
the edges and then with the predicate selected_nodes
calculates which node was visited at what time.
% g(EdgeId, From, To). g(1, 1, 2). g(2, 1, 9). g(3, 2, 3). g(4, 3, 4). g(5, 3, 9). g(6, 4, 5). g(7, 5, 6). g(8, 5, 9). g(9, 6, 7). g(10, 7, 8). g(11, 7, 9). g(12, 8, 15). g(13, 9, 10). g(14, 10, 2). g(15, 10, 11). g(16, 11, 12). g(17, 12, 2). g(18, 12, 13). g(19, 13, 14). g(20, 14, 2). g(21, 14, 15). #const start = 1. #const end = 15. edges(1..21). ix(1..21). % ensure that the index is unique { selected(Ix, Edge) : edges(Edge) } 1 :- ix(Ix). % ensure that we visit an edge atmost once { selected(Ix, Edge) : ix(Ix) } 1 :- edges(Edge). % define adjacency and add the Edge to selected adj(X, Y, I) :- g(Edge, X, Y), selected(I, Edge). adj(X, Y, I) :- g(Edge, X, Z), adj(Z, Y, I+1), selected(I, Edge). % init the problem: from start to end % with index 1) :- not adj(start, end, 1). % Here we check which nodes that was involved % in the selected edges. selected_nodes(Ix, X, Y) :- selected(Ix, Edge), g(Edge, X, Y). % minimize the number of edges #minimize [ selected(Ix, Edge) : edges(Edge) : ix(Ix) ].The solution is (edited). The first number is the order index.
selected edges: 1,2 2,13 3,15 4,16 5,18 6,19 7,21 selected_nodes 1,1,9 2,9,10 3,10,11 4,11,12 5,12,13 6,13,14 7,14,15I.e. the nodes are visited in the following order (as it should): 1,9,10,11,12,13,14,15 via the edges 2,13,15,16,18,19,21.
The second definition of
adj
:
adj(X, Y, I) :- g(Edge, X, Z), adj(Z, Y, I+1), selected(I, Edge).could as well be written with
g/3
and adj/3
swapped:
adj(X, Y, I) :- adj(Z, Y, I+1), g(Edge, X, Z), selected(I, Edge).ASP don't care about the order of rules in the predicates, in contrast to Prolog where order can matter very much.
Grid puzzles
There are quite a lot of grid puzzles in my MiniZinc collection and I have implemented some of them in ASP. The problem instances are shown below in the full list of files.minesweeper.lp: Minesweeper. This encoding was inspired by the "Phase1" encoding from Nitisha Desai's (?) .
nums(0..8). rows(1..r). cols(1..c). %a cell can be a number or a mine 1 {number(R,C,Z) : nums(Z), mine(R, C)} 1 :- rows(R), cols(C). % defining adjacency adj(R,C,R1,C1) :- rows(R;R1), cols(C;C1), |R-R1| + |C-C1|==1. adj(R,C,R1,C1) :- rows(R;R1), cols(C;C1), |R-R1|==1, |C-C1|==1. % N mines around a number N N {mine(R2, C2) : adj(R2,C2,R1,C1)} N :- number(R1,C1,N).quasigroup_completion.lp: Quasigroup completion
This is pure Latin square conditions that we saw from the Sudoku encoding:
values(1..n). % all different rows, columns, and ensure that we use % distinct values 1 { cell(Row, Col, Val) : values(Row) } 1 :- values(Col;Val). 1 { cell(Row, Col, Val) : values(Col) } 1 :- values(Row;Val). 1 { cell(Row, Col, Val) : values(Val) } 1 :- values(Row;Col).survo puzzle.lp: Survo puzzle.
The lines that handle the row and column sums are the following. Note how we extract the lower/upper bounds of the sum from the predicates
rowsum
(and colsum
).
% Row sums :- not RowSum #sum [matrix(Row, Col, Val) : values(Val) : cols(Col) = Val] RowSum, rows(Row), rowsums(Row, RowSum). % Col sums :- not ColSum #sum [matrix(Row, Col, Val) : values(Val) : rows(Row) = Val] ColSum, cols(Col), colsums(Col, ColSum).discrete_tomography.lp: Discrete tomography
hidato.lp: Hidato puzzle
strimko2.lp: Strimko puzzle
futoshiki.lp: Futoshiki puzzle
fill_a_pix.lp: Fill-a-pix puzzle
This is a Minesweeper variant where the object is to fill a picture. It's almost as the Minesweeper encoding (see above) except that "this" cell is also counted in the hints (which I tend to forget) so the sum around and including a cell can be 9 instead of 8 (as in Minesweeper). Also, the third variant of
adj/4
must be added to regard that each cell is its own adjacent.
nums(0..9). size(1..n). adj(R,C,R1,C1) :- size(R;C;R1;C1), |R-R1| + |C-C1|==1. adj(R,C,R1,C1) :- size(R;C;R1;C1), size(C1), |R-R1|==1, |C-C1|==1. adj(R,C,R,C) :- size(R;C). N { x(R2,C2) : adj(R2,C2,R1,C1) } N :- hint(R1,C1,N).seseman.lp: Seseman convent problem
coins_grid.lp: Coins grid problem
The object is to minimize the sum of the quadratic distances from the main diagonal. As noted before this is a problem that is very easy for MIP solvers, but harder for traditional CP solvers.
#const n = 10. % 31. #const c = 4. % 14. values(0..1). size(1..n). 1 { x(Row, Col, Val) : values(Val) } 1 :- size(Row;Col). c [ x(Row, Col, Val) : size(Row) : values(Val) = Val ] c :- size(Col). c [ x(Row, Col, Val) : size(Col) : values(Val) = Val ] c :- size(Row). #minimize [ x(Row, Col, Val) : values(Val) = Val*|Row-Col|*|Row-Col| ].It's interesting to see that for a small problem (
n=10, c=4
) it is much faster than for example the MiniZinc model coins_grid.mzn and Gecode/fz as solver (I have tried to get a better heuristics but not succeeded). It takes 0.93 seconds to solve this with gringo/clasp, and more than 5 minutes with Gecode/fz. Even with the solution is assigned (z = 98
) Gecode/fz takes 7 second.
A MIP solver solves the full problem (
n=31, c=14
) in 0.1 second, but it takes much longer for the ASP solver (I haven't waited for it to end).
Set covering/set parition
For some reason I like set covering and set partition problems. Most are from OR books or other sources (Winston, Taha, etc). They share a core of constraints but most have some specific twist.set_covering3.lp: Assigning senators to committee (Katta G Murty)
Here is a version where the senator is represented as integers from 1..10. As we have seen before, the problem instance is represented not as a matrix but as the predicate
senator/2
. senator(1, southern;conservative;republicans). senator(2, southern;liberals;republicans). senator(3, southern;liberals;democrats). senator(4, southern;democrats). senator(5, southern;conservative;democrats). senator(6, northern;conservative;democrats). senator(7, northern;conservative;democrats). senator(8, northern;liberals;republicans). senator(9, northern;liberals;democrats). senator(10, northern;liberals;republicans). senators(1..num_senators). groups(southern;northern;liberals;conservative;democrats;republicans). 1 { selected(Senator) : senators(Senator) : senator(Senator, Group) } :- groups(Group). #minimize [selected(Senator) : senators(Senator) ].The ";"'s in the predicates are enumerating shortcuts, so first line for senator 1 is really a shortcut for these three lines:
senator(1, southern). senator(1, conservative). senator(1, republicans).set_covering3_b.lp: Assigning senators to committee (Katta G Murty)
This is the "symbolic" version of the above.
set_covering.lp: Placing firestations (Winston: "Operations Research")
set_covering_b.lp: Placing firestations, alternative approach
set_covering2.lp: Number of security telephones on campus (Taha: "Operations Research")
set_covering4.lp: Set convering (and set partition) problem (Lundgren, Rönnqvist, Värbrand "Optimeringslära")
set_covering_opl.lp: Selecting workers to build a house (from an OPL model)
set_covering_skiena.lp: Set covering problem from Skiena
Here I use a constant
set_covering
which is default 1 which mean to run it as a set covering problem. Setting this to 0, (clingo -c set_covering=0 set_covering_skiena.lp
) it will be a set partition problem.
combinatorial_auction.lp: Combinatorial auction
bus_scheduling_csplib.lp: Bus driver scheduling from CSPLib. The problem instances (see below) are converted from CSPLib #22. I have not really tried more than the simplest problem instance (t1) with my ASP encoding.
assignment.lp: Assignment Problems from Winston "Operations Research"
ski_assignment.lp: Ski assignment problem
Asorted puzzles
And last some problems from the worlds of recreational mathematics/logic .safe_cracking.lp
This is an alphametic problem, but in contrast to send_more_money etc it is solved fast. The first version also used
x(5,C5)
in the safe_cracking
predicate and it took almost 2 seconds to solve. After commenting out this variables, it took 0.2 second.
values(1..9). % all different 1 { x(I, Val) : values(Val) } 1 :- values(I). 1 { x(I, Val) : values(I) } 1 :- values(Val). safe_cracking :- x(1,C1), x(2,C2),x(3,C3),x(4,C4), % x(5,C5), x(6,C6),x(7,C7),x(8,C8), x(9,C9), C4 - C6 == C7, C1 * C2 * C3 == C8 + C9, C2 + C3 + C6 < C8, C9 < C8. :- not safe_cracking. % no fix points :- x(I,I), values(I).marathon2.lp: Marathon puzzle (XPress)
mr_smith.lp: Smith family problem (IF Prolog), a logic problem
Here we can see how the ASP constructs can be used to express different boolean expressions.
persons(mr_smith;mrs_smith;matt;john;tim). value(go;stay). % unique indices of person 1 { action(P, T) : value(T) } 1 :- persons(P). % If Mr Smith comes, his wife will come too. action(mrs_smith, go) :- action(mr_smith, go). % At least one of their two sons Matt and John will come. 1 { action(matt, go), action(john, go) }. % Either Mrs Smith or Tim will come but not both. 1 { action(mrs_smith, go), action(tim, go) } 1. % Either Tim and John will come or neither will come. :- action(tim, T1), action(john, T2), T1 != T2. % If Matt comes then John and his father will also come. 2 { action(john, go), action(mr_smith, go) } 2 :- action(matt, go).just_forgotten.lp: Just forgotten puzzle (Enigma 1517)
place_number.lp: Place number problem
a_round_of_golf.lp: A round of gold (Dell Logic Puzzles)
The hardest part to get right in this encoding was the requirement that in MiniZinc is quite simple to state:
( (score[Frank] = score[Sands] + 4 /\ score[caddy] = score[Sands] + 7 ) \/ (score[Frank] = score[Sands] + 7 /\ score[caddy] = score[Sands] + 4 ) )I have translated it as the following. Note the integrity constraint to ensure that we don't want both of them to be false.
p3d1 :- score(frank, FrankScore), last_name(Sands, sands), first_names(Sands),first_names(Caddy), score(Sands, SandsScore), job(Caddy, caddy), score(Caddy, CaddyScore), FrankScore == SandsScore + 4, CaddyScore == SandsScore + 7. p3d2 :- score(frank, FrankScore), last_name(Sands, sands), first_names(Sands),first_names(Caddy), score(Sands, SandsScore), job(Caddy, caddy), score(Caddy, CaddyScore), FrankScore = SandsScore + 7, CaddyScore = SandsScore + 4. :- not p3d1, not p3d2. % not both false
Transitive closure
One thing that should also be mentioned is transitive closure which is some kind of trademark for Answer Set Programming (as well as planning). I have not used this much I have implemented mostly my traditional CP "learning problems" that does not use this type of structure. Here are two examples of transitive closures, and it is the succintness of these encodings that I made me so fascinated by ASP.Hamiltonian cycle
For example Hamiltonian cycle can be encoded like this in ASP. The predicatee(X,Y)
is the edge between two nodes, and v(X)
is the vertices. The cycle is hardcoded to start from node 0.
{in(X,Y)} :- e(X,Y). :- 2 {in(X,Y) : e(X,Y)}, v(X). :- 2 {in(X,Y) : e(X,Y)}, v(Y). r(X) :- in(0,X), v(X). % start from node 0 r(Y) :- r(X), in(X,Y), e(X,Y). :- not r(X), v(X).
Clique
Here is an encoding of the problem finding maximum cliques, from Wikipedia Answer_set_programming#Large_clique:v(X) :- e(X,Y). n {in(X) : v(X)}. % n {in(X) : v(X)} n. % exact size of clique % Clique criteria :- in(X), in(Y), v(X), v(Y), X!=Y, not e(X,Y), not e(Y,X). % Find maximum clique #maximize [in(X) : v(X)].I have implemented an example of the maximum clique problem in the ASP program clique.lp with the problem instances clique_data1.lp, clique_data2.lp, clique_data2.lp.
Future projects
As mentioned above, Answer Set Programming is a large subject and this blog post has only showed a small part. Here are some of my possible future projects regarding Answer Set Programming:- learn how to tweak clasp etc.
- look more into clingcon, the hybrid of ASP and CP
- look more into iclingo (another Potassco tool), an incremental grounder/solver which can be used to incrementally step different variables for example in planning problems
- planning: I first read about ASP when I was interested in automated planning so it might be time to continue this track
- transitive closures: There are a lot of fun problems that use transitive closures. One example that I have in mind is the Rogo puzzle that Mike Trick wrote about some weeks ago in Operations Research, Sudoko, Rogo, and Puzzles. ASP might be good and natural approach to this. (I did a first try with ASP on Rogo but didn't get it right...)
- DLV and other ASP grounders/solvers. There is a lot of more or less experimental tools that use different techniques and encoding schemes.
My Answer Set Programming programs
Here are my ASP programs collected for easy reference together with their problem instances. Almost all of of them have been implemented in some Constraint Programming system before, for example MiniZinc. See Common constraint programming problems for a list of different CP implementations.All are written to comply with the Potassco tools (gringo/clasp/clingo), but should be quite easy to use with to other ASP systems, e.g. Lparse/Smodels.
- 3_jugs.lp: 3 jugs problem (as a graph problem)
- a_round_of_golf.lp: A round of gold (Dell Logic Puzzles)
- all_interval.lp: All interval problem (CSPLib problem #7)
- alldifferent_except_0.lp: Alldifferent except 0
- assignment.lp: Assignment problem (from Winston "Operations Research")
- bus_scheduling.lp: Scheduling the number of buses for 6 days (from Taha "Operations Research")
- bus_scheduling_csplib.lp: Bus driver scheduling (CSPLib problem #22)
Problem instances from CSPLib problem #22:- bus_scheduling_csplib_data_c1.lp: c1
- bus_scheduling_csplib_data_c1a.lp: c1a
- bus_scheduling_csplib_data_c2.lp: c2
- bus_scheduling_csplib_data_r1.lp: r1
- bus_scheduling_csplib_data_r1a.lp: r1a
- bus_scheduling_csplib_data_r2.lp: r2
- bus_scheduling_csplib_data_r3.lp: r3
- bus_scheduling_csplib_data_r4.lp: r4
- bus_scheduling_csplib_data_r5.lp: r5
- bus_scheduling_csplib_data_r5a.lp: r5a
- bus_scheduling_csplib_data_t1.lp: t1
- bus_scheduling_csplib_data_t2.lp: t2
- clique.lp: Maximum clique problem
Problem instances: - coins_grid.lp: Coins puzzle (Tony Hurlimann)
- coloring.lp: Simple map coloring problem
- combinatorial_auction.lp: Combinatorial auction
- diet1.lp: Diet problem
- discrete_tomography.lp: Discrete tomography
Problem instances - fill_a_pix.lp: Fill-a-pix puzzle
Problem instances: - futoshiki.lp: Futoshiki puzzle
Problem instances: - hidato.lp: Hidato puzzle
Problem instances: - jobs.lp: Jobs problem (standard problem in Automated Reasoning)
- just_forgotten.lp: Just forgotten puzzle (Enigma 1517)
- langford.lp: Langford's number problem (CSP lib problem #24)
- least_diff.lp: Least diff problem
- magic_square.lp: Magic square
- marathon2.lp: Marathon puzzle (XPress)
- minesweeper.lp: Minesweeper
Problem instances:- minesweeper_data0.lp
- minesweeper_data1.lp
- minesweeper_data2.lp
- minesweeper_data3.lp
- minesweeper_data4.lp
- minesweeper_data5.lp
- minesweeper_data6.lp
- minesweeper_data7.lp
- minesweeper_data8.lp
- minesweeper_data9.lp
- minesweeper_data_basic3.lp
- minesweeper_data_basic4.lp
- minesweeper_data_basic4x4.lp
- minesweeper_data_config_page2.lp
- minesweeper_data_config_page3.lp
- minesweeper_data_german_lakshtanov.lp
- minesweeper_data_splitter.lp
- minesweeper_data_wire.lp
- mr_smith.lp: Smith family problem (IF Prolog)
- nqueens.lp: N-queens problem
- organize_day.lp: Organizing a day, simple scheduling problem
- photo.lp: Photo preference problem (from Mozart/Oz Tutorial)
- place_number.lp: Place number problem
- post_office_problem2.lp: Post office problem (Winston "Operations Research")
- quasigroup_completion.lp: Quasigroup completion
Problem instances:- quasigroup_completion_data_gomes_demo1.lp:
- quasigroup_completion_data_gomes_demo2.lp:
- quasigroup_completion_data_gomes_demo3.lp:
- quasigroup_completion_data_gomes_demo4.lp:
- quasigroup_completion_data_gomes_demo5.lp:
- quasigroup_completion_data_gomes_shmoys_p3.lp:
- quasigroup_completion_data_gomes_shmoys_p7.lp:
- quasigroup_completion_data_martin_lynce.lp:
- safe_cracking.lp: Safe cracking puzzle (Mozart/Oz)
- send_more_money.lp: SEND+MORE=MONEY
- send_more_money_any_base.lp: SEND+MORE=MONEY in "any" base
- send_most_money.lp: SEND+MOST=MONEY (maximizing MONEY)
- seseman.lp: Seseman's convent problem
- set_covering.lp: Set covering problem: placing firestations (Winston: "Operations Research")
- set_covering_b.lp: Set covering problem: placing firestations, alternative version (Winston: "Operations Research")
- set_covering2.lp: Set covering problem: number of security telephones on campus (Taha: "Operations Research")
- set_covering3.lp: Set covering problem: assigning senators to committee (Katta G Murty)
- set_covering3_b.lp: Set covering problem: assigning senators to committee, symbolic version (Katta G Murty)
- set_covering4.lp: Set convering (and partition) problem (Lundgren, Rönnqvist, Värbrand "Optimeringslära")
- set_covering_opl.lp: Set covering problem: selecting workers to build a house (from an OPL model)
- set_covering_skiena.lp: Set covering problem (Skiena)
- ski_assignment.lp: Ski assigment problem (Jeffrey Lee Hellrung, Jr)
- strimko2.lp: Strimko problem
Problem instances: - subset_sum.lp: Subset sum problem (Katta G. Murty)
- sudoku.lp: Sudoku
- survo_puzzle.lp: Survo puzzle
Problem instances: - who_killed_agatha.lp: Who killed Agatha? (The Dreadsbury Mansion Murder Mystery)
- xkcd.lp: xkcd knapsack (subset sum) problem