ASP(LC) Extended with Real Variables

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

Prototype Implementation

• MINGOR (v. 2013-04-30) uses gringo (v. 3.0.4) to ground the program, lp2mip (v. 1.15) 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.

Simple Example

• Special predicates real/1 are reserved for declaring the required binary/integer variables.
• Predicates mleq/*, mlt/*, mgeq/*, and mgt/* encode linear constraints over reals having the respective operator <=, <, >=, and >. These predicates can be renamed in the implementation if appropriate.
• A Job Shop problem is to schedule a set of tasks to be executed by a machine, which can be encoded as follows:

  #const deadline=20. task(0,"1.5","2.5"). task(1,"0.5","1.75"). task(2,"2.3","3.2"). task(3,"3.5","5.5").

  real(s(I)) :- task(I,E,D).

  real(e(I)) :- task(I,E,D).

  mgeq(1,s(I),E) :- task(I,E,D).

  mleq(1,e(I),-1,s(I),D) :- task(I,E,D).

  mgeq(1,e(I),-1,s(I),D) :- task(I,E,D).

  :- mleq(1,s(I1),-1,s(I2),0), mleq(1,s(I2),-1,e(I1),0), task(I1,E1,D1), task(I2,E2,D2), I1!=I2.

  mleq(1, e(I), deadline) :- task(I,E,D).

• The example above, stored as an instance file instance.asp and an encoding file JobShop.mingo, is run as follows
  $ mingoR.sh instance.asp JobShop.mingo
SATISFIABLE
Vars: delta=0.000001 s(3)=7.950003 s(2)=4.750002 s(1)=0.500000 s(0)=2.250001 e(3)=13.450003 e(2)=7.950002 e(1)=2.250000 e(0)=4.750001 (other values 0).
  
• In the output, the positive value of delta means that a schedule is found where the starting times of the tasks are given by the variables of the form s(i).
  

Related Articles

G. Liu, T. Janhunen, and I. Niemelä: Introducing Real Variables and MIP Objective Functions to Answer Set Programming. Submitted for publication.