TY - JOUR

T1 - Boosting Answer Set Optimization with Weighted Comparator Networks

AU - Bomanson, Jori

AU - Janhunen, Tomi

PY - 2020/7

Y1 - 2020/7

N2 - 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, for example, to find the best size for a given benchmark class. Experiments show accelerated optimization performance on several benchmark problems.

AB - 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, for example, to find the best size for a given benchmark class. Experiments show accelerated optimization performance on several benchmark problems.

KW - answer set programming

KW - comparator network

KW - normalization

KW - optimization rewriting

KW - translation

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

U2 - 10.1017/S147106842000006X

DO - 10.1017/S147106842000006X

M3 - Article

AN - SCOPUS:85084804770

SN - 1471-0684

VL - 20

SP - 512

EP - 551

JO - Theory and Practice of Logic Programming

JF - Theory and Practice of Logic Programming

IS - 4

ER -