Complex Optimization

Problem Description

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. To this end, the MetaASP encodings (http://www.cs.uni-potsdam.de/wv/metasp/) implement complex preferences and optimization criteria, for instance, inclusion-based minimization or Pareto efficiency, by means of meta-programming.

We apply a MetaASP-style encoding to represent inclusion-based minimization tasks stemming from three distinct domains:

1. Biological Network Repair 2. Linux Package Configuration 3. Maximal Satisfiable Clause Set

Our encoding induces decision problems expressed by (proper) disjunctive programs. Integer constants and functional terms are used as identifiers; they are tightly correlated to and thus bounded by terms occurring in inputs facts.

Predicates

• Input: rule/2, set/2, wlist/4, minimize/2, optimize/3, hide/0, show/1

• Output: hold/1

Input format

Output format

Example(s)

Given the input:

wlist(0,0,pos(atom(q)),1). wlist(0,1,pos(atom(r)),1). 
set(0,neg(atom(c))). rule(pos(sum(0,0,2)),pos(conjunction(0))).
set(1,pos(atom(r))). rule(pos(atom(a)),pos(conjunction(1))).
set(2,neg(atom(d))). rule(pos(sum(0,0,2)),pos(conjunction(2))).
set(3,neg(atom(t))). rule(pos(atom(d)),pos(conjunction(3))).
wlist(1,0,pos(atom(p)),1). wlist(1,1,pos(atom(t)),1).
set(4,pos(atom(a))). set(4,neg(atom(b))).
rule(pos(sum(0,1,2)),pos(conjunction(4))). set(5,pos(atom(t))).
set(5,neg(atom(r))). set(5,neg(atom(s))).
rule(pos(atom(b)),pos(conjunction(5))). set(6,neg(atom(r))).
set(6,neg(atom(q))). rule(pos(atom(s)),pos(conjunction(6))).
set(7,pos(atom(s))). rule(pos(atom(a)),pos(conjunction(7))).
rule(pos(atom(a)),pos(conjunction(3))). set(8,neg(atom(p))).
rule(pos(atom(c)),pos(conjunction(8))). set(9,pos(atom(a))).
set(9,neg(atom(t))). set(9,neg(atom(b))).
set(9,neg(atom(p))). rule(pos(false),pos(conjunction(9))).
set(10,pos(atom(q))). set(10,pos(atom(r))).
set(10,neg(atom(c))). rule(pos(false),pos(conjunction(10))).
set(11,pos(atom(q))). set(11,pos(atom(r))). set(11,neg(atom(d))).
rule(pos(false),pos(conjunction(11))). set(12,pos(atom(r))).
set(12,pos(atom(t))). set(12,neg(atom(b))). set(12,neg(atom(q))).
rule(pos(false),pos(conjunction(12))).
wlist(2,0,pos(atom(q)),1). wlist(2,1,pos(atom(r)),1).
wlist(2,2,pos(atom(p)),1). wlist(2,3,pos(atom(s)),1).

minimize(1,2). optimize(1,1,incl).

:- not hold(atom(r)), not hold(atom(t)).

The example above consists of facts reifying a small non-disjunctive logic program along with a subset-minimization objective. Combined with the (standard-conform) (meta-)encoding, a (meta-)answer set represents a subset-minimal answer set of the reified non-disjunctive program. However, the example also includes an integrity constraint on (meta-)answer sets, thus posting a query whether a matching subset-minimal answer set exists.

In this case, there are two (meta-)answer sets represented by true atoms of output predicate hold/1. These atoms are as follows:

Solution 1:

hold(atom(t)). hold(conjunction(8)). hold(conjunction(7)). hold(atom(s)).
hold(conjunction(6)). hold(conjunction(4)). hold(atom(a)). hold(conjunction(2)).
hold(atom(c)).

Solution 2:

hold(atom(r)). hold(atom(p)). hold(conjunction(3)). hold(conjunction(4)).
hold(atom(a)). hold(atom(d)). hold(conjunction(1)). hold(conjunction(0)).

Additional sample instances: download

Problem Peculiarities

Type: Synthetic Competition: System Track

The submitted instances should be (medium) hard for current disjunctive ASP systems, that is, neither trivial nor completely out of range. Performance can and should vary between instances, which do not obey any regular pattern we would be aware of.

Notes and Updates

Change: Our Linux Package Configuration benchmarks turned out to yield huge ground programs, and we have thus decided to restrict our submission bundle to instances from Domain 1 and 3.

Author(s)

• Authors: Martin Gebser, Roland Kaminski, Torsten Schaub
  • Affiliation: University of Potsdam, Germany