Re: [Potassco-users] Enumerate Top-N Models

[Roland K. <kam...@cs...>]

On Thursday, May 24, 2018 10:09:41 AM CEST Peter Schueller wrote:
> Dear Dominik,
> 
> Below is an example adapted from the clingo repo. It adds a nogood when
> receiving a model. The model is counted as valid model for the optimization.
> 
> I had some negative experiences with this type of adding a clause/nogood:
> if one of the literals is a fact, there is no error but the nogood has no
> effect, it is silently ignored.
If you add a nogood and the literal is true on level zero, then this literal 
should have no effect. The remaining literals in the nogood should still have 
an effect. If the literal is false, then the nogood should have no effect 
because it is always satisfied. Anything else is a bug. Please report such 
issues if you stumble upon them.

> Also, with optimization I had other cases where adding a nogood in on_model
> still yielded models afterwards that violated the nogood. (Symmetric
> models?)
This also sounds like a bug.

> 
> Still, the code below can be a starting point, maybe it will work nicely
> for you. The example below works.
> 
> If you want to reject models before they can be counted as optimal, you
> need to implement a custom propagator (also possible in the Python API) and
> add nogoods in the check() function. This always worked nicely for me but
> it requires management of solver literals (not trivial but not highly
> complex either).
This is not a good idea to approach Dominik's problem. Nogoods learned during 
model enumeration disappear when the solve call finishes. Using the backend or 
maybe grounding additional rules is the better route.

> Best,
> Peter
> 
> % example from clingo repo
> #script (python)
> import clingo
> def main(prg):
>    def on_model(m):
>        m.context.add_nogood([(clingo.Function("c",[clingo.Number(1)]),
> True)])
>        #m.context.add_clause([(clingo.Function("a"), False),
> (clingo.Function("b"), False)])
>        #m.context.add_nogood([(clingo.Function("c"), True),
> (clingo.Function("d"), True)])
>    prg.configuration.solve.models = 0
>    prg.ground([("base", [])])
>    prg.solve(on_model=on_model)
>    print ("and again")
>    prg.solve()
> #end.
> 2 { a(1); b(1); c(1); d(1) }.
> 
> 
> 
> On Thu, May 24, 2018 at 7:56 AM, Dominik Moritz <dom...@cs...>
> wrote:
> > Hi All,
> > 
> > I'm still stuck at the point where I add the constraint. How do I specify
> > a constraint that forbids models with some cost lower than some threshold?
> > 
> > An alternative idea I had is that instead of adding a weight constraint, I
> > could add an integrity constraint that forbids the same model to appear
> > again. So when the solver finds `b(2,1) b(3,1)`, I would add `:- b(2,1),
> > b(3,1).`.
> > 
> > I believe that I can achieve this with `model.symbols(shown=True)` and
> > then adding a rule with `prg.backend.add_rule([], ...)` but I can't figure
> > out what goes in the ...
> > 
> > I'm concerned that while this approach could work, there are going to be
> > weird interactions with projected models. I think that I need to use
> > `shown=True` when models are projected and `atoms=True, terms=True` when
> > model projection is off. Is that correct?
> > 
> > Any help is greatly appreciated,
> > Dominik
> > 
> > On Sun, May 20, 2018 at 2:18 PM Dominik Moritz
> > <dom...@cs...>
> > 
> > wrote:
> >> Hi Roland,
> >> 
> >> Thank you for your answer. I am trying to implement your solution but got
> >> stuck at the point where I add a new constraint.
> >> 
> >> Here is my code so far:
> >> 
> >> #script(python)
> >> def main(prg):
> >> prg.ground([('base', [])])
> >> 
> >> count = 5
> >> 
> >> while count > 0:
> >> cost = None
> >> with prg.solve(yield_=True) as handle:
> >> for model in handle:
> >> if model.optimality_proven:
> >> cost = model.cost
> >> 
> >> count -= 1
> >> if count == 0:
> >> # We have enough results so let's cancel the search
> >> handle.cancel()
> >> # add a weight constraint forbidding models greater or equal to the
> >> current bound
> >> TODO
> >> 
> >> #end.
> >> 
> >> a(1..3,1).
> >> a(3..6,2).
> >> a(6..9,3).
> >> a(9..12,4).
> >> 
> >> 2 { b(X,C): a(X,C) } 10.
> >> 
> >> :~ b(X,C). [C,X]
> >> 
> >> #show b/2.
> >> 
> >> Can you give me a hint about what I need to add?
> >> 
> >> Thank you,
> >> Dominik
> >> 
> >> On Wed, Mar 21, 2018 at 4:22 PM Roland Kaminski <
> >> 
> >> kam...@cs...> wrote:
> >>> You can do this via clingo's Python API without restarting the solver.
> >>> Similar
> >>> to the way you describe it. Set the optimization mode to optN to
> >>> enumerate
> >>> models. If you get too few models, add a weight constraint forbidding
> >>> models
> >>> greater or equal to the current bound. Then repeat the search.
> >>> 
> >>> You have to implement this enumeration scheme yourself because clingo
> >>> does not
> >>> provide anything like this out of the box.
> >>> 
> >>> You still have to restart the search but learnt information will be kept
> >>> and
> >>> no regrounding is necessary. -R
> >>> 
> >>> https://potassco.org/clingo/python-api/current/clingo.html
> >>> 
> >>> On Wednesday, March 21, 2018 11:59:47 PM CET Dominik Moritz wrote:
> >>> > Hi Potassco users,
> >>> > 
> >>> > What's the smartest way to enumerate the top-N models in
> >>> > clingo? `--opt-mode=optN -n 100` prints up to 100 optimal models but
> >>> 
> >>> does
> >>> 
> >>> > not print models that are not optimal but close to optimal.
> >>> 
> >>> Unfortunately,
> >>> 
> >>> > I don't know the bound I want to use and so `--opt-mode=enum` won't
> >>> 
> >>> work
> >>> 
> >>> > for me either.
> >>> > 
> >>> > The only option I see right now is to run clingo once, get all optimal
> >>> > models, then run it again but disallow all models that were returned
> >>> 
> >>> in the
> >>> 
> >>> > previous step and repeat this process until I found enough models.
> >>> > 
> >>> > Thank you,
> >>> > Dominik
> > 
> > ------------------------------------------------------------
> > ------------------
> > Check out the vibrant tech community on one of the world's most
> > engaging tech sites, Slashdot.org! http://sdm.link/slashdot
> > _______________________________________________
> > Potassco-users mailing list
> > Pot...@li...
> > https://lists.sourceforge.net/lists/listinfo/potassco-users