asprin
a general framework for qualitative and quantitative optimization in answer set programming

asprin is a general framework for optimization in ASP that allows

Some preference types (subset, pareto...) are already defined in the asprin library,
but many more can be defined simply writing a logic program.

For a formal description of asprin, please read our paper.

asprin source code and precompiled binaries for Linux, Mac and Windows are available here.

The User Guide of asprin appears in Section 10.2 of the Potassco User Guide, available here.
Follows a short tutorial that is part of the Guide.


Tutorial



A Simple Example

Let's start with program example1.lp, that we call the base program, and the clingo execution:

gr(1..5).

1 { m(1) ; m(2) ; m(3) } 1.   

a(1)    :- m(1).
b(1..5) :- m(1).

a(1..2) :- m(2).
b(1)    :- m(2).

a(5)    :- m(3).
b(2..5) :- m(3). 

#show m/1. #show a/1. #show b/1.
$ clingo-4 example1.lp 0
...
Answer: 1
m(2) a(1) a(2) b(1) 
Answer: 2
m(3) a(5) b(2) b(3) b(4) b(5) 
Answer: 3
m(1) a(1) b(1) b(2) b(3) b(4) b(5)

We get three stable models, one with m(1), one with m(2) and another with m(3). We call them M1, M2 and M3.

Now let's find the stable models of the base program that are subset minimal with respect to predicate a/1.
We write the following preference specification in preference1.lp:

#preference(p1,subset){                                                                                             
  a(X) : gr(X)                                                                                                    
}.
#optimize(p1).

The first three lines define a preference statement of name p1 and type subset that contains one preference element
"a(X) :- gr(X)". The body of the preference element has to be formed by domain predicates of the base program.
Intuitively, the preference statement defines a preference of type subset over atoms of predicate a/1.
The last line is an optimize statement that instructs asprin to compute stable models that are optimal with respect to p1.

We are ready to compute one optimal stable model:

$ asprin example1.lp preference1.lp asprin.lib
asprin version 1.0
Answer: 1
m(2) a(2) a(1) b(1)
Answer: 2
m(1) a(1) b(4) b(3) b(5) b(2) b(1)
OPTIMUM FOUND

Models       : 1
  Enumerated : 2

File asprin.lib is the preference library of asprin, it is a logic program implementing many preference types.
In the execution first asprin finds the stable model M2 of the base program. Then it looks for a stable model that is preferred to M2 and finds M1. In the last step asprin looks for a stable model that is preferred to M1, and given that no one is found this proves the optimality of M1. In total, one optimal model was computed, and two stable models were enumerated.

If we want to minimize both a/1 and b/1, we can use the preference specification of preference2.lp:

#preference(p2,subset){                                                                                             
  a(X) : gr(X);                                                                                                   
  b(X) : gr(X)                                                                                                    
}.
#optimize(p2).

Then we get that M2 is already an optimal stable model:

$ ./asprin example1.lp preference2.lp asprin.lib
asprin version 1.0
Answer: 1
m(2) a(2) a(1) b(1)
OPTIMUM FOUND

Models       : 1
  Enumerated : 1


Computing Many Optimal Stable Models

As in clingo, in asprin we can compute n optimal models adding the number n to the command line, where 0 is used to compute all optimal models.

$ ./asprin example1.lp preference1.lp asprin.lib 0
asprin version 1.0
Answer: 1
m(2) a(2) a(1) b(1)
Answer: 2
m(1) a(1) b(4) b(3) b(5) b(2) b(1)
OPTIMUM FOUND
Answer: 3
m(3) a(5) b(4) b(3) b(5) b(2)
OPTIMUM FOUND

Models       : 2
  Enumerated : 3

asprin runs as before for computing one optimal model. Then it searches for a stable model of the base program that is not worse than M1, finds M3 and proves that it is optimal. In the last step, asprin looks for some stable model that is not worse than M1 and M3, and given that there is none, it finishes. It has enumerated 3 stable models, 2 of which are optimal.

if we add a file c1.lp:

{c(1)}.
#show c/1.

then we get two optimal stable models more, that contain c(1):

$ ./asprin example1.lp preference1.lp asprin.lib c1.lp 0
asprin version 1.0
Answer: 1
m(2) a(2) a(1) b(1)
Answer: 2
m(1) a(1) b(4) b(3) b(5) b(2) b(1)
OPTIMUM FOUND
Answer: 3
m(1) a(1) b(4) b(3) b(5) b(2) b(1) c(1)
OPTIMUM FOUND *
Answer: 4
m(3) a(5) b(4) b(3) b(5) b(2)
OPTIMUM FOUND
Answer: 5
m(3) a(5) b(4) b(3) b(5) b(2) c(1)
OPTIMUM FOUND *

Models       : 4
  Enumerated : 5
  

When asprin looks for a stable model that is not worse than M1, first it looks for models that interpret the same way as M1 the atoms that appear in the preference statements. This way it finds the second optimal model, that contains c(1), and prints it followed by the line "OPTIMUM FOUND *". Then it continues searching, finds M3 and the process continues.

We can project the optimal models on the atoms of the preference statements with option --project:

$ ./asprin example1.lp preference1.lp asprin.lib c1.lp 0 --project
asprin version 1.0
Answer: 1
m(2) a(2) a(1) b(1)
Answer: 2
m(1) a(1) b(4) b(3) b(5) b(2) b(1)
OPTIMUM FOUND
Answer: 3
m(3) a(5) b(4) b(3) b(5) b(2)
OPTIMUM FOUND

Models       : 2
  Enumerated : 3
  


More Preference Types

The library of asprin, asprin.lib, implements the following basic preference types:

[1] Gerhard Brewka, Ilkka Niemela, Miroslaw Truszczynski: Answer Set Optimization. IJCAI 2003: 867-872.
[2] Emanuele Di Rosa, Enrico Giunchiglia, Marco Maratea: Solving satisfiability problems with preferences. Constraints 15(4): 485-515 (2010).

For example, we can minimize the cardinality of the atoms of predicate b/1 as follows:

#preference(p3,less(cardinality)){                                                                                             
  b(X) : gr(X)                                                                                                    
}.
#optimize(p3).
$ ./asprin example1.lp preference3.lp asprin.lib 0
asprin version 1.0
Answer: 1
m(2) a(2) a(1) b(1)
OPTIMUM FOUND

Models       : 1
  Enumerated : 1
  

The library of asprin implements the following composite preference types:

They all have appeared in:

[3] Tran Cao Son, Enrico Pontelli: Planning with preferences using logic programming. TPLP 6(5): 559-607 (2006).

As an example, in preference4.lp we can apply a pareto preference p4 on top of p1 and p3:

#preference(p1,subset){                                                                                             
  a(X) : gr(X)                                                                                                    
}.
#preference(p3,less(cardinality)){                                                                                             
  b(X) : gr(X)                                                                                                    
}.
#preference(p4,pareto){
  name(p1);
  name(p3)
}.
#optimize(p4).
$ ./asprin example1.lp preference4.lp asprin.lib 0
asprin version 1.0
Answer: 1
m(2) a(2) a(1) b(1)
OPTIMUM FOUND
Answer: 2
m(3) a(5) b(5) b(4) b(3) b(2)
OPTIMUM FOUND
Answer: 3
m(1) a(1) b(5) b(4) b(3) b(2) b(1)
OPTIMUM FOUND

Models       : 3
  Enumerated : 3

Or in preference5.lp we apply a lexicographic order p5 giving priority to p1 over p3:

#preference(p1,subset){                                                                                             
  a(X) : gr(X)                                                                                                    
}.
#preference(p3,less(cardinality)){                                                                                             
  b(X) : gr(X)                                                                                                    
}.
#preference(p5,lexico){
  2 :: name(p1);
  1 :: name(p3)
}.
#optimize(p5).
$ ./asprin example1.lp asprin.lib preference5.lp 0
asprin version 1.0
Answer: 1
m(2) a(2) a(1) b(1)
Answer: 2
m(1) a(1) b(5) b(4) b(3) b(2) b(1)
OPTIMUM FOUND
Answer: 3
m(3) a(5) b(5) b(4) b(3) b(2)
OPTIMUM FOUND

Models       : 2
  Enumerated : 3
  


Help

asprin is part of Potassco, the Potsdam Answer Set Solving Collection, hosted at Sourceforge.

For any comments, just drop us a message!


Follow us at G+ SourceForge.net Logo Valid XHTML 1.0 Strict Valid CSS!