Rewriting optimization statements in answer-set programs
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2016-11-01
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
15
Series
Technical Communications of the 32nd International Conference on Logic Programming, ICLP 2016, Volume 52
Abstract
Constraints on Pseudo-Boolean (PB) expressions can be translated into Conjunctive Normal Form (CNF) using several known translations. In Answer-Set Programming (ASP), analogous expressions appear in weight rules and optimization statements. Previously, we have translated weight rules into normal rules, using normalizations designed in accord with existing CNF encodings. In this work, we rededicate such designs to rewrite optimization statements in ASP. In this context, a rewrite of an optimization statement is a replacement accompanied by a set of normal rules that together replicate the original meaning. The goal is partially the same as in translating PB constraints or weight rules: to introduce new meaningful auxiliary atoms that may help a solver in the search for (optimal) solutions. In addition to adapting previous translations, we present selective rewriting techniques in order to meet the above goal while using only a limited amount of new rules and atoms. We experimentally evaluate these methods in preprocessing ASP optimization statements and then searching for optimal answer sets. The results exhibit significant advances in terms of numbers of optimally solved instances, reductions in search conflicts, and shortened computation times. By appropriate choices of rewriting techniques, improvements are made on instances involving both small and large weights. In particular, we show that selective rewriting is paramount on benchmarks involving large weights.Description
Keywords
Answer-set programming, Pseudo-Boolean optimization, Translation methods
Other note
Citation
Bomanson, J, Gebser, M & Janhunen, T 2016, Rewriting optimization statements in answer-set programs . in M Carro, A King, N Saeedloei & M De Vos (eds), Technical Communications of the 32nd International Conference on Logic Programming, ICLP 2016 . vol. 52, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Conference on Logic Programming, New York City, United States, 16/10/2016 . https://doi.org/10.4230/OASIcs.ICLP.2016.5