ASP(LC)

This is an extension of answer set programming (ASP) where rules and linear constraints over integers are used together for modelling.

Prototype Implementation

• MINGO (v. 2012-09-30) uses gringo (v. 3.0.3) to ground the program, lp2mip (v. 1.16) to translate it into mixed integer program, and an appropriate MIP solver (such as cplex, v. 12.5) to compute answer sets.
• Scripts/instructions for downloading third-party software are provided.
• There are some benchmarks available (see our KR'12 paper for details).

Simple Example

• Special predicates bin/1 and int/1 are reserved for declaring the required binary/integer variables.
• Predicates mleq/*, mlt/*, mgeq/*, and mgt/* encode linear constraints over integers having the respective operator <=,<,>=, and >. These predicates can be renamed in the implementation if appropriate.
• A sorting problem that is to sort a set of numbers in increasing order is encoded as follows:

  number(6;30;22;16;27;48;3;36).

  int(position(X)) :- number(X).

  :- mlt(1,position(X),1), number(X).

  :- mleq(1,position(X1),-1,position(X2),0), mgeq(1,position(X1),-1,position(X2),0), number(X1;X2), X1!= X2.

  :- mlt(1,position(X1),-1,position(X2),0), number(X1;X2), X1>X2.

• The example above, stored as sorting.mingo, is run as follows
  $ mingo.sh sorting.mingo
SATISFIABLE
number(6) number(30) number(22) number(16) number(27) number(48) number(3) number(36)
Theory: mgeq(1,position(36),-1,position(3),0) ... (Relation predicates satisfied by the answer set)
Vars: position(36)=7 position(3)=1 position(48)=8 position(27)=5 position(16)=3 position(22)=4 position(30)=6 position(6)=2

Related Publications

G. Liu, T. Janhunen, and I. Niemelä: Answer Set Programming via Mixed Integer Programming. In T. Eiter and S. McIlraith, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 13th International Conference (KR'12), 32—42, Rome, Italy, June 2012. AAAI Press.