Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-25T04:23:43.216Z Has data issue: false hasContentIssue false
  • English
  • Français

Combining Answer Set Programming and domain heuristics for solving hard industrial problems (Application Paper)

Published online by Cambridge University Press:  14 October 2016

CARMINE DODARO Open the ORCID record for CARMINE DODARO [Opens in a new window] ,
PHILIP GASTEIGER ,
NICOLA LEONE ,
BENJAMIN MUSITSCH ,
FRANCESCO RICCA  and
KOSTYANTYN SHCHEKOTYKHIN
CARMINE DODARO
Affiliation:
Department of Mathematics and Computer Science, University of Calabria, Italy (e-mail: [email protected])
PHILIP GASTEIGER
Affiliation:
Alpen-Adria-Universität Klagenfurt, Austria (e-mail: [email protected])
NICOLA LEONE
Affiliation:
Department of Mathematics and Computer Science, University of Calabria, Italy (e-mail: [email protected])
BENJAMIN MUSITSCH
Affiliation:
Alpen-Adria-Universität Klagenfurt, Austria (e-mail: [email protected])
FRANCESCO RICCA
Affiliation:
Department of Mathematics and Computer Science, University of Calabria, Italy (e-mail: [email protected])
KOSTYANTYN SHCHEKOTYKHIN
Affiliation:
Alpen-Adria-Universität Klagenfurt, Austria (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Answer Set Programming (ASP) is a popular logic programming paradigm that has been applied for solving a variety of complex problems. Among the most challenging real-world applications of ASP are two industrial problems defined by Siemens: the Partner Units Problem (PUP) and the Combined Configuration Problem (CCP). The hardest instances of PUP and CCP are out of reach for state-of-the-art ASP solvers. Experiments show that the performance of ASP solvers could be significantly improved by embedding domain-specific heuristics, but a proper effective integration of such criteria in off-the-shelf ASP implementations is not obvious. In this paper the combination of ASP and domain-specific heuristics is studied with the goal of effectively solving real-world problem instances of PUP and CCP. As a byproduct of this activity, the ASP solver wasp was extended with an interface that eases embedding new external heuristics in the solver. The evaluation shows that our domain-heuristic-driven ASP solver finds solutions for all the real-world instances of PUP and CCP ever provided by Siemens.

Keywords

Answer Set ProgrammingDomain HeuristicsIndustrial Applications
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 16 , Special Issue 5-6: 32nd International Conference on Logic Programming , September 2016 , pp. 653 - 669
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Albrecht, A. 1979. Measuring Application Development Productivity. In IBM Application Development Symp., I. B. M. Press, Ed. Proc. of IBM Application Development Symp., 83–92.Google Scholar
Alviano, M., Dodaro, C., Leone, N. and Ricca, F. 2015. Advances in WASP. In Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Lexington, KY, USA, September 27-30, 2015. Proceedings, Calimeri, F., Ianni, G., and Truszczynski, M., Eds. Lecture Notes in Computer Science, vol. 9345. Springer, 40–54.Google Scholar
Aschinger, M., Drescher, C., Friedrich, G., Gottlob, G., Jeavons, P., Ryabokon, A. and Thorstensen, E. 2011a. Optimization methods for the partner units problem. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 8th International Conference, CPAIOR 2011, Berlin, Germany, May 23-27, 2011. Proceedings, Achterberg, T. and Beck, J. C., Eds. Lecture Notes in Computer Science, vol. 6697. Springer, 4–19.Google Scholar
Aschinger, M., Drescher, C., Gottlob, G., Jeavons, P. and Thorstensen, E. 2011b. Tackling the partner units configuration problem. In IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, Walsh, T., Ed. IJCAI/AAAI, 497–503.Google Scholar
Balduccini, M. 2011. Learning and using domain-specific heuristics in ASP solvers. AI Commun. 24, 2, 147–164.Google Scholar
Balduccini, M., Gelfond, M., Watson, R. and Nogueira, M. 2001. The usa-advisor: A case study in answer set planning. In Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR 2001, Vienna, Austria, September 17-19, 2001, Proceedings, Eiter, T., Faber, W., and Truszczynski, M., Eds. Lecture Notes in Computer Science, vol. 2173. Springer, 439–442.Google Scholar
Baral, C. and Uyan, C. 2001. Declarative specification and solution of combinatorial auctions using logic programming. In Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR 2001, Vienna, Austria, September 17-19, 2001, Proceedings, Eiter, T., Faber, W., and Truszczynski, M., Eds. Lecture Notes in Computer Science, vol. 2173. Springer, 186–199.Google Scholar
Biere, A., Heule, M., van Maaren, H. and Walsh, T., Eds. 2009. Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press.Google Scholar
Brewka, G., Eiter, T. and Truszczynski, M. 2011. Answer set programming at a glance. Commun. ACM 54, 12, 92–103.Google Scholar
Calimeri, F., Gebser, M., Maratea, M. and Ricca, F. 2016. Design and results of the fifth answer set programming competition. Artif. Intell. 231, 151–181.Google Scholar
Campeotto, F., Dovier, A. and Pontelli, E. 2015. A declarative concurrent system for protein structure prediction on GPU. J. Exp. Theor. Artif. Intell. 27, 5, 503–541.Google Scholar
Dantsin, E., Eiter, T., Gottlob, G. and Voronkov, A. 2001. Complexity and expressive power of logic programming. ACM Comput. Surv. 33, 3, 374–425.Google Scholar
Dodaro, C., Leone, N., Nardi, B. and Ricca, F. 2015. Allotment problem in travel industry: A solution based on ASP. In Web Reasoning and Rule Systems - 9th International Conference, RR 2015, Berlin, Germany, August 4-5, 2015, Proceedings, ten Cate, B. and Mileo, A., Eds. Lecture Notes in Computer Science, vol. 9209. Springer, 77–92.Google Scholar
Drescher, C. 2012. The partner units problem a constraint programming case study. In IEEE 24th International Conference on Tools with Artificial Intelligence, ICTAI 2012, Athens, Greece, November 7-9, 2012. IEEE Computer Society, 170–177.Google Scholar
Eén, N. and Sörensson, N. 2003. An extensible sat-solver. In Theory and Applications of Satisfiability Testing, 6th International Conference, SAT 2003. Santa Margherita Ligure, Italy, May 5-8, 2003 Selected Revised Papers, Giunchiglia, E. and Tacchella, A., Eds. Lecture Notes in Computer Science, vol. 2919. Springer, 502–518.Google Scholar
Erdem, E. and Öztok, U. 2015. Generating explanations for biomedical queries. Theory and Practice of Logic Programming 15, 1, 35–78.Google Scholar
Erdem, E., Patoglu, V., Saribatur, Z. G., Schüller, P. and Uras, T. 2013. Finding optimal plans for multiple teams of robots through a mediator: A logic-based approach. Theory and Practice of Logic Programming 13, 4–5, 831–846.Google Scholar
Falkner, A. A., Haselböck, A., Schenner, G. and Schreiner, H. 2011. Modeling and solving technical product configuration problems. AI EDAM 25, 2, 115–129.Google Scholar
Falkner, A. A., Ryabokon, A., Schenner, G. and Shchekotykhin, K. M. 2015. OOASP: connecting object-oriented and logic programming. In Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Lexington, KY, USA, September 27-30, 2015. Proceedings, Calimeri, F., Ianni, G., and Truszczynski, M., Eds. Lecture Notes in Computer Science, vol. 9345. Springer, 332–345.Google Scholar
Fionda, V. and Greco, G. 2013. The complexity of mixed multi-unit combinatorial auctions: Tractability under structural and qualitative restrictions. Artif. Intell. 196, 1–25.CrossRefGoogle Scholar
Friedrich, G. 2015. Industrial success stories of ASP and CP: What's still open? Joint invited talk at ICLP and CP 2015 - http://booleconferences.ucc.ie/iclp2015speakers.Google Scholar
Gaggl, S. A., Manthey, N., Ronca, A., Wallner, J. P. and Woltran, S. 2015. Improved answer-set programming encodings for abstract argumentation. Theory and Practice of Logic Programming 15, 4–5, 434–448.Google Scholar
Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Romero, J. and Schaub, T. 2015a. Progress in clasp series 3. In Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Lexington, KY, USA, September 27-30, 2015. Proceedings, Calimeri, F., Ianni, G., and Truszczynski, M., Eds. Lecture Notes in Computer Science, vol. 9345. Springer, 368–383.Google Scholar
Gebser, M., Kaminski, R., König, A. and Schaub, T. 2011. Advances in gringo series 3. In Logic Programming and Nonmonotonic Reasoning - 11th International Conference, LPNMR 2011, Vancouver, Canada, May 16-19, 2011. Proceedings, Delgrande, J. P. and Faber, W., Eds. Lecture Notes in Computer Science, vol. 6645. Springer, 345–351.Google Scholar
Gebser, M., Kaufmann, B., Romero, J., Otero, R., Schaub, T. and Wanko, P. 2013. Domain-specific heuristics in answer set programming. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA., desJardins, M. and Littman, M. L., Eds. AAAI Press.Google Scholar
Gebser, M., Maratea, M. and Ricca, F. 2015b. The sixth answer set programming competition web site. http://aspcomp2015.dibris.unige.it/.Google Scholar
Gebser, M., Ryabokon, A. and Schenner, G. 2015c. Combining heuristics for configuration problems using answer set programming. In Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Lexington, KY, USA, September 27-30, 2015. Proceedings, Calimeri, F., Ianni, G., and Truszczynski, M., Eds. Lecture Notes in Computer Science, vol. 9345. Springer, 384–397.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Comput. 9, 3/4, 365–386.CrossRefGoogle Scholar
Grasso, G., Leone, N., Manna, M. and Ricca, F. 2011. ASP at work: Spin-off and applications of the DLV system. In Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning - Essays Dedicated to Michael Gelfond on the Occasion of His 65th Birthday, Balduccini, M. and Son, T. C., Eds. Lecture Notes in Computer Science, vol. 6565. Springer, 432–451.Google Scholar
Hoos, H., Lindauer, M. T. and Schaub, T. 2014. claspfolio 2: Advances in algorithm selection for answer set programming. Theory and Practice of Logic Programming 14, 4–5, 569–585.Google Scholar
Koponen, L., Oikarinen, E., Janhunen, T. and Säilä, L. 2015. Optimizing phylogenetic supertrees using answer set programming. Theory and Practice of Logic Programming 15, 4–5, 604–619.CrossRefGoogle Scholar
Manna, M., Ricca, F. and Terracina, G. 2015. Taming primary key violations to query large inconsistent data via ASP. Theory and Practice of Logic Programming 15, 4–5, 696–710.CrossRefGoogle Scholar
Maratea, M., Pulina, L. and Ricca, F. 2014. A multi-engine approach to answer-set programming. Theory and Practice of Logic Programming 14, 6, 841–868.Google Scholar
Marileo, M. C. and Bertossi, L. E. 2010. The consistency extractor system: Answer set programs for consistent query answering in databases. Data Knowl. Eng. 69, 6, 545–572.Google Scholar
Ryabokon, A. 2015. Knowledge-based (Re)configuration of Complex Products and Services. Ph.D. thesis, Alpen-Adria-University Klagenfurt.Google Scholar
Teppan, E. C., Friedrich, G. and Falkner, A. A. 2012. Quickpup: A heuristic backtracking algorithm for the partner units configuration problem. In Proceedings of the Twenty-Fourth Conference on Innovative Applications of Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada, Fromherz, M. P. J. and Muñoz-Avila, H., Eds. AAAI.Google Scholar
Supplementary material: PDF

Dodaro supplementary material

Online Appendix

Download Dodaro supplementary material(PDF)
PDF 187.6 KB