Boosting Answer Set Optimization with Weighted Comparator Networks
From MaRDI portal
Abstract: Answer set programming (ASP) is a paradigm for modeling knowledge intensive domains and solving challenging reasoning problems. In ASP solving, a typical strategy is to preprocess problem instances by rewriting complex rules into simpler ones. Normalization is a rewriting process that removes extended rule types altogether in favor of normal rules. Recently, such techniques led to optimization rewriting in ASP, where the goal is to boost answer set optimization by refactoring the optimization criteria of interest. In this paper, we present a novel, general, and effective technique for optimization rewriting based on comparator networks, which are specific kinds of circuits for reordering the elements of vectors. The idea is to connect an ASP encoding of a comparator network to the literals being optimized and to redistribute the weights of these literals over the structure of the network. The encoding captures information about the weight of an answer set in auxiliary atoms in a structured way that is proven to yield exponential improvements during branch-and-bound optimization on an infinite family of example programs. The used comparator network can be tuned freely, e.g., to find the best size for a given benchmark class. Experiments show accelerated optimization performance on several benchmark problems.
Recommendations
- Computing Weighted Solutions in Answer Set Programming
- scientific article; zbMATH DE number 7455735
- Complex optimization in answer set programming
- Improving the normalization of weight rules in answer set programs
- Scalable neural-probabilistic answer set programming
- Optimizing answer set computation via heuristic-based decomposition
- ANSWER SET PROGRAMMING AND COMBINATORIAL MULTICRITERIA DECISION MAKING
- On optimal solutions of answer set optimization problems
- Abstract answer set solvers with backjumping and learning
Cites work
- scientific article; zbMATH DE number 5139161 (Why is no real title available?)
- A New Look at BDDs for Pseudo-Boolean Constraints
- A Permutation Network
- Abstract answer set solvers with backjumping and learning
- Advances in WASP
- Answer set programming as a modeling language for course timetabling
- Answer set solving with lazy nogood generation
- Benchmarking curriculum-based course timetabling: formulations, data formats, instances, validation, visualization, and results
- Conflict-driven answer set solving: from theory to practice
- Extended ASP Tableaux and rule redundancy in normal logic programs
- Improving the normalization of weight rules in answer set programs
- Learning discrete decomposable graphical models via constraint optimization
- Logic programming and nonmonotonic reasoning. 13th international conference, LPNMR 2015, Lexington, KY, USA, September 27--30, 2015. Proceedings
- Logic programming and nonmonotonic reasoning. 14th international conference, LPNMR 2017, Espoo, Finland, July 3--6, 2017. Proceedings
- MaxHS
- Multi-level Algorithm Selection for ASP
- Normalizing cardinality rules using merging and sorting constructions
- On abstract modular inference systems and solvers
- Optimum stable model search: algorithms and implementation
- Progress in clasp series 3
- Rewriting optimization statements in answer-set programs
- Solving SAT and SAT modulo theories, from an abstract Davis-Putnam-Logemann-Loveland procedure to \(\operatorname{DPLL}(T)\)
- Tableau calculi for logic programs under answer set semantics
- The Design of the Sixth Answer Set Programming Competition
- The design of the Seventh Answer Set Programming Competition
- The implicit hitting set approach to solve combinatorial optimization problems with an application to multigenome alignment
- Unsatisfiability-based optimization in clasp
- Why are there so many loop formulas?
- \textsc{lp2normal} -- a normalization tool for extended logic programs
This page was built for publication: Boosting Answer Set Optimization with Weighted Comparator Networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4957202)
