Combining answer set programming and domain heuristics for solving hard industrial problems (application paper)

DOI10.1017/S1471068416000284MaRDI QIDQ4593048zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Carmine Dodaro, Philip Gasteiger, N. Leone, Benjamin Musitsch, F. Ricca, Kostyantyn Shchekotykhin

Publication date 9 November 2017

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.00730

zbMATH Keywords

answer set programmingindustrial applicationsdomain heuristics

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Logic programming (68N17)

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. This paper is under consideration for acceptance in TPLP.

Recommendations

• Combining Heuristics for Configuration Problems Using Answer Set Programming
• Learning domain-specific heuristics for answer set solvers
• Learning and using domain-specific heuristics in ASP solvers
• Industrial-size scheduling with ASP+CP
• The power of non-ground rules in Answer Set Programming

Cites work

• scientific article; zbMATH DE number 25190 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1884390 (Why is no real title available?)
• scientific article; zbMATH DE number 1890629 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• claspfolio2: Advances in Algorithm Selection for Answer Set Programming
• Advances in WASP
• Combining Heuristics for Configuration Problems Using Answer Set Programming
• Design and results of the Fifth Answer Set Programming Competition
• Finding optimal plans for multiple teams of robots through a mediator: a logic-based approach
• Generating explanations for biomedical queries
• Improved answer-set programming encodings for abstract argumentation
• Learning and using domain-specific heuristics in ASP solvers
• Logic programming, knowledge representation, and nonmonotonic reasoning. Essays dedicated to Michael Gelfond on the occasion of his 65th birthday
• Optimization Methods for the Partner Units Problem
• Optimizing phylogenetic supertrees using answer set programming
• Progress in clasp series 3
• Taming primary key violations to query large inconsistent data via ASP
• The complexity of mixed multi-unit combinatorial auctions: tractability under structural and qualitative restrictions
• Theory and Applications of Satisfiability Testing
• Web reasoning and rule systems. 9th international conference, RR 2015, Berlin, Germany, August 4--5, 2015. Proceedings

Cited in

(21)

• Logic Programming
• Combining Heuristics for Configuration Problems Using Answer Set Programming
• Generating event-sequence test cases by answer set programming with the incidence matrix
• Better paracoherent answer sets with less resources
• ASP and subset minimality: enumeration, cautious reasoning and MUSes
• Paracoherent answer set computation
• Efficient Lifting of Symmetry Breaking Constraints for Complex Combinatorial Problems
• Cautious reasoning in ASP via minimal models and unsatisfiable cores
• Lifting symmetry breaking constraints with inductive logic programming
• scientific article; zbMATH DE number 7453100 (Why is no real title available?)
• Debugging non-ground ASP programs: technique and graphical tools
• Partial compilation of ASP programs
• Learning and using domain-specific heuristics in ASP solvers
• Technical note. Efficiently coupling the \(\mathscr{I}\)-DLV grounder with ASP solvers
• Domain-Specific Heuristics in Answer Set Programming: A Declarative Non-Monotonic Approach
• Beyond NP: quantifying over answer sets
• The External Interface for Extending WASP
• Deep learning for the generation of heuristics in answer set programming: a case study of graph coloring
• Adaptive large-neighbourhood search for optimisation in answer-set programming
• Learning domain-specific heuristics for answer set solvers
• Shared aggregate sets in answer set programming

Describes a project that uses

Uses Software

• OOASP
• claspfolio 2
• WASP
• clasp
• Gringo
• MiniSat

This page was built for publication: Combining answer set programming and domain heuristics for solving hard industrial problems (application paper)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4593048)