Closed robertoasin closed 2 years ago
Clingo (or better clasp since this is about solving) can handle weight constraints natively. By default it translates certain simple constraints. Have a look at the following example:
{ p(1..10) }.
x :- not 2 { p(X) }.
y :- 1 { p(X) }.
An at most one constraint would correspond to the one in the rule deriving x
. (Note that not 2 { p(X) }
is strongly equivalent to { p(X) } 1
.) You can actually inspect what is happening using the tools shipping with clingo:
% clingo example.lp --pre | lpconvert --text
y :- x_11.
{p(1);p(2);p(3);p(4);p(5);p(6);p(7);p(8);p(9);p(10)}.
x_11 :- p(1).
x_11 :- p(2).
x_11 :- p(3).
x_11 :- p(4).
x_11 :- p(5).
x_11 :- p(6).
x_11 :- p(7).
x_11 :- p(8).
x_11 :- p(9).
x_11 :- p(10).
x_13 :- 2{p(1); p(2); p(3); p(4); p(5); p(6); p(7); p(8); p(9); p(10)}.
x :- not x_13.
The rule deriving x_13
indicates that clasp is handling the at most one constraint natively while the rules deriving x_11
show that the at least one constraint has been translated. We also published a paper about the implementation: https://link.springer.com/chapter/10.1007%2F978-3-642-02846-5_23.
Great.
Thank you very much for the answer.
What also comes to my mind is that Jori and Tomi did quite some work to translate weight constraints. Maybe you find Jori's thesis interesting: https://aaltodoc.aalto.fi/handle/123456789/46911. The lp2normal might be interesting...
Thank you,
These are great links to review.
El mié, 6 oct 2021 a las 11:13, Roland Kaminski @.***>) escribió:
What also comes to my mind is that Jori and Tomi did quite some work to translate weight constraints. Maybe you find Jori's thesis interesting: https://aaltodoc.aalto.fi/handle/123456789/46911. The lp2normal https://research.ics.aalto.fi/software/asp/download/ might be interesting...
— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/potassco/clingo/issues/338#issuecomment-936313954, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAKUFKVSGI3SUKEW53WFEY3UFRKSFANCNFSM5FORR5YQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.
Hi,
We're preparing a paper on our results on a new ASP and MaxSAT encoding for MAPF, which beats current state-of-the-art solvers on dense scenarios and, for that, we need to know how clingo handles cardinality (i.e. at-most-one) constraints. Can the solver handle this kind of constraints natively or are they grounded to propositional clauses. In the later case, which encoding for cardinality constraints do you use?