Rewriting optimization statements in answer-set programs

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

Standard

Rewriting optimization statements in answer-set programs. / Bomanson, Jori; Gebser, Martin; Janhunen, Tomi.

Technical Communications of the 32nd International Conference on Logic Programming, ICLP 2016. toim. / Manuel Carro; Andy King; Neda Saeedloei; Marina De Vos. Vuosikerta 52 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. 5.

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

Harvard

Bomanson, J, Gebser, M & Janhunen, T 2016, Rewriting optimization statements in answer-set programs. julkaisussa M Carro, A King, N Saeedloei & M De Vos (toim), Technical Communications of the 32nd International Conference on Logic Programming, ICLP 2016. Vuosikerta. 52, 5, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, New York City, Yhdysvallat, 16/10/2016. https://doi.org/10.4230/OASIcs.ICLP.2016.5

APA

Bomanson, J., Gebser, M., & Janhunen, T. (2016). Rewriting optimization statements in answer-set programs. teoksessa M. Carro, A. King, N. Saeedloei, & M. De Vos (Toimittajat), Technical Communications of the 32nd International Conference on Logic Programming, ICLP 2016 (Vuosikerta 52). [5] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/OASIcs.ICLP.2016.5

Vancouver

Bomanson J, Gebser M, Janhunen T. Rewriting optimization statements in answer-set programs. julkaisussa Carro M, King A, Saeedloei N, De Vos M, toimittajat, Technical Communications of the 32nd International Conference on Logic Programming, ICLP 2016. Vuosikerta 52. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2016. 5 https://doi.org/10.4230/OASIcs.ICLP.2016.5

Author

Bomanson, Jori ; Gebser, Martin ; Janhunen, Tomi. / Rewriting optimization statements in answer-set programs. Technical Communications of the 32nd International Conference on Logic Programming, ICLP 2016. Toimittaja / Manuel Carro ; Andy King ; Neda Saeedloei ; Marina De Vos. Vuosikerta 52 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016.

Bibtex - Lataa

@inproceedings{50bb038f171d452496d8bc15968eabc0,
title = "Rewriting optimization statements in answer-set programs",
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.",
keywords = "Answer-set programming, Pseudo-Boolean optimization, Translation methods",
author = "Jori Bomanson and Martin Gebser and Tomi Janhunen",
year = "2016",
month = "11",
day = "1",
doi = "10.4230/OASIcs.ICLP.2016.5",
language = "English",
volume = "52",
editor = "Manuel Carro and Andy King and Neda Saeedloei and {De Vos}, Marina",
booktitle = "Technical Communications of the 32nd International Conference on Logic Programming, ICLP 2016",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
address = "Germany",

}

RIS - Lataa

TY - GEN

T1 - Rewriting optimization statements in answer-set programs

AU - Bomanson, Jori

AU - Gebser, Martin

AU - Janhunen, Tomi

PY - 2016/11/1

Y1 - 2016/11/1

N2 - 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.

AB - 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.

KW - Answer-set programming

KW - Pseudo-Boolean optimization

KW - Translation methods

UR - http://www.scopus.com/inward/record.url?scp=85004144102&partnerID=8YFLogxK

U2 - 10.4230/OASIcs.ICLP.2016.5

DO - 10.4230/OASIcs.ICLP.2016.5

M3 - Conference contribution

VL - 52

BT - Technical Communications of the 32nd International Conference on Logic Programming, ICLP 2016

A2 - Carro, Manuel

A2 - King, Andy

A2 - Saeedloei, Neda

A2 - De Vos, Marina

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ER -

ID: 9934982