Complex Optimization in Answer Set Programming

Preference handling and optimization are indispensable means for addressing non-trivial applications in Answer Set Programming (ASP). However, their implementation becomes difficult whenever they bring about a significant increase in computational complexity. As a consequence, existing ASP systems do not offer complex optimization capacities, supporting, for instance, inclusion-based minimization or Pareto efficiency. Here we provide a collection of encodings that implement such complex preferences and optimization criteria by means of meta-programming.

The encodings (version of 25/05/2012) can conveniently be used by piping the reified output of gringo back into gringo, now ran in conjunction with meta-encodings, and then launching claspD for solving. This workflow is illustrated by small examples shipped together with the encodings. We also provide large instances stemming from an application in systems biology. Details on encodings and the biological application can be found in the paper "Complex Optimization in Answer Set Programming: Extended Version". The results obtained on a selection of instances (run sequentially on a machine equipped with Intel Xeon E5520 processors and 48 GB main memory under Linux) indicate the competitiveness of meta-programming in comparison to direct encoding.


You will need grounder gringo and solver claspD. Both are available from the Potassco project page.

The example calls assume that you are using a bash (compatible) shell. (Depending on your shell, you might need to adjust the calls.)