Re: [Potassco-users] --opt-heu?

[Benjamin K. <kau...@cs...>]

Hi,

> Does anyone have a concise explanation of what the --opt-heu? I'm
> interested to know under which conditions I can predict clasp's first guess
> in optimization problems.

--opt-heu (i.e. --opt-heu=1) enables a static sign heuristic.
It *does not* change how/which variables are picked by the main
heuristic but simply sets the preferred sign of variables contained
in minimize statements s.th. the literal occurring in the minimize
statement is first set to false.

> Consider the following two programs. Each asks for a way to roll 100 dice
> so that the sum of the faces is minimized. With some quick mental analysis,
> 100 is clearly the optimal answer (rolling a 1 for each die).
>
> Here's the first program:
>
> die(1..100).
> face(1..6).
> 1 { roll(D,F):face(F) } 1 :- die(D).
> #minimize [ roll(D,F)=F ].
>
> For this, "clingo 1 --stats" finds the opt=100 solution on the first try.
> Well, after 500 (why 500?) choices, it finds a solution without hitting any
> conflicts.
>
> Here's the second program: (F -->  7-F basically numbers the faces backwards)
>
> die(1..100).
> face(1..6).
> 1 { roll(D,F):face(F) } 1 :- die(D).
> #minimize [ roll(D,F)=7-F ].
>
> With and without "--opt-heu", clingo's first guess is actually the worst
> (opt=600). Interestingly, picking vsids instead of berkmin as the heuristic
> finds opt=101 as the first solution (almost 100, but not quite).

First, why the 500 choices: There are 100 1{...}1 rules, each with 6
atoms. By default, clasp's decision heuristic prefers to set atoms
to false. Hence, for each rule five atoms are chosen to false and
the last one is then derived to true.

Regarding --opt-heu: In both programs, the minimize statement contains
positive literals. So, --opt-heu makes the negative literal the
preferred one. Given that this is already the default literal for atoms
and there are no conflicts influencing the heuristic, --opt-heu
actually has no effect.

The reason for the observed optimize values is accidental: initially,
there are no heuristic values for the variables - they are simply
picked in the order defined by the underlying data structure
(an array in case of Berkmin, a heap in case of VSIDs).
Furthermore, in the first example, variables with lower id have higher
weight, while in the second example the opposite holds.


As an interesting remark: If you call clasp with "--trans-ext=choice",
choices drop to 100 and the observed optimize values are interchanged.
In that case, clasp introduces rules and aux-atoms like
roll_aux(100,6) :- not roll(100,6).
roll(100,6)     :- not roll_aux(100,6).
...

The heuristic then picks and falsifies the aux atom first
so that the corresponding roll()-atoms is derived to true.

Best regards,
Ben