= 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: [[https://www.mat.unical.it/aspcomp2013/files/samples/complex_optimization-sample.zip|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