Boosting Answer Set Optimization with Weighted Comparator Networks

Autor: Jori Bomanson, Tomi Janhunen
Přispěvatelé: Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences, Tampere University
Rok vydání: 2020
Předmět:
FOS: Computer and information sciences
Normalization (statistics)
Computer Science - Logic in Computer Science
Translation
Theoretical computer science
Boosting (machine learning)
Comparator
Computer science
0102 computer and information sciences
02 engineering and technology
computer.software_genre
01 natural sciences
Theoretical Computer Science
Answer set programming
Artificial Intelligence
0202 electrical engineering
electronic engineering
information engineering
Comparator network
Tietojenkäsittely ja informaatiotieteet - Computer and information sciences
Answer Set Programming
Logic in Computer Science (cs.LO)
Exponential function
Normalization
Computational Theory and Mathematics
Code refactoring
010201 computation theory & mathematics
Hardware and Architecture
Computer Science::Programming Languages
F.4.1
020201 artificial intelligence & image processing
Rewriting
computer
Software
Optimization rewriting
Zdroj: Theory and Practice of Logic Programming. 20:512-551
ISSN: 1475-3081
1471-0684
DOI: 10.1017/s147106842000006x
Popis: 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.
Comment: 36 pages
Databáze: OpenAIRE
Externí odkaz: