Answer set programming (ASP) is a declarative language for nonmonotonic reasoning based on stable model semantics. A stable model is a classical model of the input program satisfying the following stability condition: only necessary information is included in the model under the assumptions provided by the model itself for the unknown knowledge in the program, where unknown knowledge is encoded by means of default negation. Rational agents acting in the real world often have to reason in presence of unknown knowledge. It is also common that real world agents cannot meet all their desiderata. For this reason, ASP programs may include weak constraints for representing numerical preferences over jointly incompatible conditions. Stable models are therefore associated with a cost given by the unsatisfied weak constraints, and stable models of minimum cost are preferred. This paper summarizes algorithms and strategies for computing optimal stable models, and hints on how these algorithms can be extended to handle some qualitative preferences that have a natural representation in circumscription, that is, those based on subset-minimality and superset-maximality.
AlvianoM., Optimization problems in answer set programming. In Joint Proceedings of the 18th Italian Conference on Theoretical Computer Science and the 32nd Italian Conference on Computational Logic, CEUR Workshop Proceedings, volume 1949, 2017, pp. 1–5, URL, http://ceur-ws.org/Vol-1949/invited1.pdf
3.
AlvianoM., The ingredients of the argumentation reasoner pyglaf: Python, circumscription, and glucose to taste. Proceedings of the 24th RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion 2017 (RCRA 2017) A workshop of the XVI International Conference of the Italian Association for Artificial Intelligence (AI*IA 2017), Bari, Italy, November 14, 2017, CEUR Workshop Proceedings, volume 2011, 2017, pp. 1–16.
4.
AlvianoM., The pyglaf argumentation reasoner. In Technical Communications of the 33rd International Conference on Logic Programming, ICLP 2017 TCs, August 28-September 1, 2017, Melbourne, Australia, 2017 To appear.
AlvianoM. and DodaroC., Answer set enumeration via assumption literals. In
AdorniGiovanni,
CagnoniStefano,
GoriMarco and MarateaMarco, editors, AI*IA 2016: Advances in Artificial Intelligence - XVth International Conference of the Italian Association for Artificial Intelligence, Genova, Italy, November 29 - December 1, 2016, Proceedings, volume 10037 of LNCS, 2016, pp. 149–163. Springer. doi: 10.1007/978-3-319-49130-1_12. URL http://dx.doi.org/10.1007/978-3-319-49130-1_12
.
AlvianoM. and DodaroC., Unsatisfiable core shrinking for anytime answer set optimization. In
SierraCarles, editor, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, 2017, pp. 4781–4785. ijcai.org. doi: 10.24963/ijcai.2017/666. URL https://doi.org/10.24963/ijcai.2017/66
9.
AlvianoM. and FaberW., The complexity boundary of answer set programming with generalized atoms under the FLP semantics. In
CabalarPedro and SonTran Cao, editors, Logic Programming and Nonmonotonic Reasoning, 12th International Conference, LPNMR 2013, Corunna, Spain, September 15-19, 2013. Proceedings, volume 8148 of Lecture Notes in Computer Science, 2013, pp. 67–72. Springer. doi: 10.1007/978-3-642-40564-8_7. URL https://doi.org/10.1007/978-3-642-40564-8_
AlvianoM., DodaroC., LeoneN. and RiccaF., Advances in WASP. In
CalimeriFrancesco,
IanniGiovambattista and TruszczynskiMiroslaw, editors, Proceedings of Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, volume 9345 of LNCS, 2015, pp. 40–54. Springer. doi: 10.1007/978-3-319-23264-5_5. URL http://dx.doi.org/10.1007/978-3-319-23264-5_
AlvianoM., DodaroC. and RiccaF., A maxsat algorithm using cardinality constraints of bounded size. In
YangQiang and WooldridgeMichael, editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, 2015, pp. 2677–2683. AAAI Press. URL http://ijcai.org/Abstract/15/379
AlvianoM., CalimeriF., DodaroC., FuscáD., LeoneN., PerriS., RiccaF., VeltriP. and ZangariJ., The ASP system DLV2. In
BalducciniMarcello and
JanhunenTomi, editors, Logic Programming and Nonmonotonic Reasoning - 14th International Conference, LPNMR 2017, Espoo, Finland, July 3-6, 2017, Proceedings, volume 10377 of Lecture Notes in Computer Science, 2017, pp. 215–221. Springer. doi: 10.1007/978-3-319-61660-5_19. URL https://doi.org/10.1007/978-3-319-61660-5_1
16.
AlvianoM., DodaroC. and MarateaM., An advanced answer set programming encoding for nurse scheduling. In
EspositoFloriana,
BasiliRoberto,
FerilliStefano and LisiF. A, editors, AI*IA 2017 Advances in Artificial Intelligence - XVIth International Conference of the Italian Association for Artificial Intelligence, Bari, Italy, November 14-17, 2017, Proceedings, volume 10640 of Lecture Notes in Computer Science, 2017, pp. 468–482. Springer. doi: 10.1007/978-3-319-70169-1_35. URL https://doi.org/10.1007/978-3-319-70169-1_3
17.
AndresB., KaufmannB., MatheisO. and SchaubT., Unsatisfiability-based optimization in clasp. In
DovierAgostino and
CostaVítor Santos, editors, Technical Communications of the 28th International Conference on Logic Programming, ICLP 2012, volume 17 of LIPIcs, pp. 211–221. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012. doi: 10.4230/LIPIcs.ICLP.2012.211. URL http://dx.doi.org/10.4230/LIPIcs.ICLP.2012.21
18.
AndresB., BiewerA., RomeroJ., HaubeltC. and SchaubT., Improving coordinated smt-based system synthesis by utilizing domain-specific heuristics. In
CalimeriFrancesco,
IanniGiovambattista and TruszczynskiMiroslaw, editors, Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Lexington, KY, USA, September 27- 30, 2015. Proceedings, volume 9345 of Lecture Notes in Computer Science, 2015, pp. 55–68. Springer. doi: 10.1007/978-3-319-23264-5_6. URL https://doi.org/10.1007/978-3-319-23264-5_
19.
AnsóteguiC., BonetM.L. and LevyJ., Solving (weighted) partial maxsat through satisfiability testing. In
KullmannOliver, editor, Proceedings of Theory and Applications of Satisfiability Testing, SAT 2009, volume 5584 of Lecture Notes in Computer Science, 2009, pp. 427–440. Springer. doi: 10.1007/978-3-642-02777-2_39. URL http://dx.doi.org/10.1007/978-3-642-02777-2_3
BalducciniM., GelfondM., WatsonR. and NogueiraM., The usa-advisor: A case study in answer set planning. In
EiterThomas,
FaberWolfgang, and TruszczynskiMiroslaw, editors, Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR 2001, Vienna, Austria, September 17-19, 2001, Proceedings, volume 2173 of Lecture Notes in Computer Science, 2001, pp. 439–442. Springer. doi: 10.1007/3-540-45402-0_39. URL https://doi.org/10.1007/3-540-45402-0_3
BaralC. and UyanC., Declarative specification and solution of combinatorial auctions using logic programming. In
EiterThomas,
FaberWolfgang, and TruszczynskiMiroslaw, editors, Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR 2001, Vienna, Austria, September 17-19, 2001, Proceedings, volume 2173 of Lecture Notes in Computer Science, 2001, pp. 186–199. Springer. doi: 10.1007/3-540-45402-0_14. URL https://doi.org/10.1007/3-540-45402-0_1
BliemB., KaufmannB., SchaubT. and WoltranS., ASP for Anytime Dynamic Programming on Tree Decompositions. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, AAAI Press, 2016.
28.
BruynoogheM., BlockeelH., BogaertsB., de CatB.,
De PooterS.,
JansenJ.,
LabarreA.,
RamonJ.,
DeneckerM. and VerwerS., Predicate logic as a modeling language: Modeling and solving some machine learning and data mining problems with IDP3, TPLP15(6) (2015), 783–817
. doi: 10.1017/S147106841400009X. URL https://doi.org/10.1017/S147106841400009X
ChaB., IwamaK., KambayashiY. and MiyazakiS., Local search algorithms for partial MAXSAT. In Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, 1997, pp. 263–268. AAAI Press/The MIT Press.
FaberW., PfeiferG., LeoneN., Dell’ArmiT. and IelpaG., Design and implementation of aggregate functions in the DLV system, TPLP8(5-6) (2008), 545–580. doi: 10.1017/S1471068408003323
FuZ. and MalikS., On Solving the Partial MAXSAT Problem. In
BiereArmin and GomesC. P, editors, Proceedings of Theory and Applications of Satisfiability Testing, SAT 2006, volume 4121 of Lecture Notes in Computer Science, 2006, pp. 252–265. Springer. doi: 10.1007/11814948_ 25. URL http://dx.doi.org/10.1007/11814948_2
39.
GebserM., KaufmannB. and SchaubT., Conflict-driven answer set solving: From theory to practice, Artif Intell187 (2012), 52–89
. doi: 10.1016/j.artint.2012.04.001
40.
GebserM., KaminskiR., KaufmannB., RomeroJ. and SchaubT., Progress in clasp series 3. In
CalimeriFrancesco,
IanniGiovambattista, and TruszczynskiMiroslaw, editors, Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Lexington, KY, USA, September 27-30, 2015. Proceedings, volume 9345 of Lecture Notes in Computer Science, 2015, pp. 368–383. Springer. doi: 10.1007/978-3-319-23264-5_31. URL https://doi.org/10.1007/978-3-319-23264-5_3
41.
GebserM., RyabokonA. and SchennerG., Combining heuristics for configuration problems using answer set programming. In
CalimeriFrancesco,
IanniGiovambattista, and TruszczynskiMiroslaw, editors, Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Lexington, KY, USA, September 27-30, 2015. Proceedings, volume 9345 of Lecture Notes in Computer Science, 2015, pp. 384–397. Springer. doi: 10.1007/978-3-319-23264-5_32. URL https://doi.org/10.1007/978-3-319-23264-5_3
42.
GelfondM. and KahlY., , ISBN, Knowledge Representation, Reasoning, and the Design of Intelligent Agents: The Answer- Set Programming Approach, Cambridge University Press, 2014. ISBN 978-1107029569.
GiunchigliaE., LierlerY. and MarateaM., Answer set programming based on propositional satisfiability, J Autom Reasoning36(4) (2006), 345–377. doi: 10.1007/s10817-006-9033-2
LierlerY. and MarateaM., Cmodels-2: Sat-based answer set solver enhanced to non-tight programs. In
LifschitzVladimir and NiemeläIlkka, editors, Logic Programming and Nonmonotonic Reasoning, 7th International Conference, LPNMR 2004, Fort Lauderdale, FL, USA, January 6-8, 2004, Proceedings, volume 2923 of Lecture Notes in Computer Science, 2004, pp. 346–350. Springer. doi: 10.1007/978-3-540-24609-1_32. URL https://doi.org/10.1007/978-3-540-24609-1_3
LifschitzV., Answer set programming and plan generation, Artificial Intelligence138 (2002), 39–54.
52.
LiuG., JanhunenT. and NiemeläI., Answer Set Programming via Mixed Integer Programming. In
BrewkaGerhard,
EiterThomas and McIlraithSheila A., editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012. AAAI Press, 2012. URL http://www.aaai.org/ocs/index.php/KR/KR12/paper/view/4516
53.
ManquinhoV.M., Marques SilvaJ.P. and
PlanesJ., Algorithms for weighted boolean optimization. In KullmannOliver, editor, Proceedings of Theory and Applications of Satisfiability Testing, SAT 2009 volume 5584 of Lecture Notes in Computer Science, 2009, pp. 495–508. Springer. doi: 10.1007/978-3-642-02777-2_45. URL http://dx.doi.org/10.1007/978-3-642-02777-2_4
MarekV.W. and TruszczyńskiM., Stable models and an alternative logic programming paradigm. In
AptKrzysztof R.,
WiktorMarek V.,
TruszczyńskiMirosław and
WarrenDavid S., editors, The Logic Programming Paradigm – A 25-Year Perspective, 1999, pp. 375–398. Springer Verlag.
56.
MariënM., WittocxJ., DeneckerM. and BruynoogheM., SAT(ID): Satisfiability of propositional logic extended with inductive definitions. In Hans Kleine Büning and Xishun Zhao, editors, Theory and Applications of Satisfiability Testing - SAT 11th International Conference, SAT Guangzhou, China, May 12-15, Proceedings, volume 4996 of Lecture Notes in Computer Science, 2008, pp. 211–224. Springer. doi: 10.1007/978-3-540-79719-7_20. URL https://doi.org/10.1007/978-3-540-79719-7_2
Marques-SilvaJ. and ManquinhoV.M., Towards more effective unsatisfiability-based maximum satisfiability algorithms. In
BüningHans Kleine and ZhaoXishun, editors, Proceedings of Theory and Applications of Satisfiability Testing, SAT 2008, volume 4996 of Lecture Notes in Computer Science, 2008, pp. 225–230. Springer. doi: 10.1007/978-3-540-79719-7_21. URL http://dx.doi.org/10.1007/978-3-540-79719-7_2
59.
Marques-SilvaJ. and PlanesJ., Algorithms for Maximum Satisfiability using Unsatisfiable Cores. In Design, Automation and Test in Europe, DATE 2008, 2008, pp. 408–413, Munich, Germany, IEEE.
MorgadoA., DodaroC. and Marques-SilvaJ., Core-Guided MaxSAT with Soft Cardinality Constraints. In Proceedings of Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, 2014, pp. 564–573, Lyon, France, Springer.
62.
NadelA., Boosting minimal unsatisfiable core extraction. In
BloemRoderick and SharyginaNatasha, editors, Proceedings of 10th International Conference on Formal Methods in Computer-Aided Design, FMCAD 2010, 2010, pp. 221–229. IEEE. URL http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5770953
NarodytskaNina and BacchusF., Maximum satisfiability using core-guided maxsat resolution. In
BrodleyCarla E. and
StonePeter, editors, Proceedings of the Twenty- Eighth AAAI Conference on Artificial Intelligence, July 27 - 31, 2014, Québec City, Québec, Canada, 2014, pp. 2717–2723. AAAI Press. URL http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8513
65.
NguyenV., ObermeierP., SonT.C., SchaubT. and YeohW., Generalized target assignment and path finding using answer set programming. In
SierraCarles, editor, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, 2017, pp. 1216–1223. ijcai.org. doi: 10.24963/ijcai.2017/169. URL https://doi.org/10.24963/ijcai.2017/16
66.
NiemeläI., Logic programming with stable model semantics as constraint programming paradigm, Annals of Mathematics and Artificial Intelligence25(3– 4) (1999), 241–273.
