TY  - JOUR
A1  - Banbara, Mutsunori
A1  - Soh, Takehide
A1  - Tamura, Naoyuki
A1  - Inoue, Katsumi
A1  - Schaub, Torsten H.
T1  - Answer set programming as a modeling language for course timetabling
JF  - Theory and practice of logic programming
N2  - The course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. The modeling language for course timetabling is required to be expressive enough to specify a wide variety of soft constraints and objective functions. Furthermore, the resulting encoding is required to be extensible for capturing new constraints and for switching them between hard and soft, and to be flexible enough to deal with different formulations. In this paper, we propose to make effective use of ASP as a modeling language for course timetabling. We show that our ASP-based approach can naturally satisfy the above requirements, through an ASP encoding of the curriculum-based course timetabling problem proposed in the third track of the second international timetabling competition (ITC-2007). Our encoding is compact and human-readable, since each constraint is individually expressed by either one or two rules. Each hard constraint is expressed by using integrity constraints and aggregates of ASP. Each soft constraint S is expressed by rules in which the head is the form of penalty (S, V, C), and a violation V and its penalty cost C are detected and calculated respectively in the body. We carried out experiments on four different benchmark sets with five different formulations. We succeeded either in improving the bounds or producing the same bounds for many combinations of problem instances and formulations, compared with the previous best known bounds.
KW  - answer set programming
KW  - educational timetabling
KW  - course timetabling
Y1  - 2013
U6  - https://doi.org/10.1017/S1471068413000495
SN  - 1471-0684
VL  - 13
IS  - 2
SP  - 783
EP  - 798
PB  - Cambridge Univ. Press
CY  - New York
ER  - 
TY  - JOUR
A1  - Hoos, Holger
A1  - Kaminski, Roland
A1  - Lindauer, Marius
A1  - Schaub, Torsten H.
T1  - aspeed: Solver scheduling via answer set programming
JF  - Theory and practice of logic programming
N2  - Although Boolean Constraint Technology has made tremendous progress over the last decade, the efficacy of state-of-the-art solvers is known to vary considerably across different types of problem instances, and is known to depend strongly on algorithm parameters. This problem was addressed by means of a simple, yet effective approach using handmade, uniform, and unordered schedules of multiple solvers in ppfolio, which showed very impressive performance in the 2011 Satisfiability Testing (SAT) Competition. Inspired by this, we take advantage of the modeling and solving capacities of Answer Set Programming (ASP) to automatically determine more refined, that is, nonuniform and ordered solver schedules from the existing benchmarking data. We begin by formulating the determination of such schedules as multi-criteria optimization problems and provide corresponding ASP encodings. The resulting encodings are easily customizable for different settings, and the computation of optimum schedules can mostly be done in the blink of an eye, even when dealing with large runtime data sets stemming from many solvers on hundreds to thousands of instances. Also, the fact that our approach can be customized easily enabled us to swiftly adapt it to generate parallel schedules for multi-processor machines.
KW  - algorithm schedules
KW  - answer set programming
KW  - portfolio-based solving
Y1  - 2015
U6  - https://doi.org/10.1017/S1471068414000015
SN  - 1471-0684
SN  - 1475-3081
VL  - 15
SP  - 117
EP  - 142
PB  - Cambridge Univ. Press
CY  - New York
ER  - 
TY  - JOUR
A1  - Gebser, Martin
A1  - Janhunen, Tomi
A1  - Rintanen, Jussi
T1  - Declarative encodings of acyclicity properties
JF  - Journal of logic and computation
N2  - Many knowledge representation tasks involve trees or similar structures as abstract datatypes. However, devising compact and efficient declarative representations of such structural properties is non-obvious and can be challenging indeed. In this article, we take a number of acyclicity properties into consideration and investigate various logic-based approaches to encode them. We use answer set programming as the primary representation language but also consider mappings to related formalisms, such as propositional logic, difference logic and linear programming. We study the compactness of encodings and the resulting computational performance on benchmarks involving acyclic or tree structures.
KW  - acyclicity properties
KW  - logic-based modeling
KW  - answer set programming
KW  - satisfiability
Y1  - 2015
U6  - https://doi.org/10.1093/logcom/exv063
SN  - 0955-792X
SN  - 1465-363X
VL  - 30
IS  - 4
SP  - 923
EP  - 952
PB  - Oxford Univ. Press
CY  - Eynsham, Oxford
ER  - 
TY  - JOUR
A1  - Gebser, Martin
A1  - Schaub, Torsten H.
A1  - Thiele, Sven
A1  - Veber, Philippe
T1  - Detecting inconsistencies in large biological networks with answer set programming
JF  - Theory and practice of logic programming
N2  - We introduce an approach to detecting inconsistencies in large biological networks by using answer set programming. To this end, we build upon a recently proposed notion of consistency between biochemical/genetic reactions and high-throughput profiles of cell activity. We then present an approach based on answer set programming to check the consistency of large-scale data sets. Moreover, we extend this methodology to provide explanations for inconsistencies by determining minimal representations of conflicts. In practice, this can be used to identify unreliable data or to indicate missing reactions.
KW  - answer set programming
KW  - bioinformatics
KW  - consistency
KW  - diagnosis
Y1  - 2011
U6  - https://doi.org/10.1017/S1471068410000554
SN  - 1471-0684
VL  - 11
IS  - 5-6
SP  - 323
EP  - 360
PB  - Cambridge Univ. Press
CY  - New York
ER  - 
TY  - JOUR
A1  - Frioux, Clémence
A1  - Schaub, Torsten H.
A1  - Schellhorn, Sebastian
A1  - Siegel, Anne
A1  - Wanko, Philipp
T1  - Hybrid metabolic network completion
JF  - Theory and practice of logic programming
N2  - Metabolic networks play a crucial role in biology since they capture all chemical reactions in an organism. While there are networks of high quality for many model organisms, networks for less studied organisms are often of poor quality and suffer from incompleteness. To this end, we introduced in previous work an answer set programming (ASP)-based approach to metabolic network completion. Although this qualitative approach allows for restoring moderately degraded networks, it fails to restore highly degraded ones. This is because it ignores quantitative constraints capturing reaction rates. To address this problem, we propose a hybrid approach to metabolic network completion that integrates our qualitative ASP approach with quantitative means for capturing reaction rates. We begin by formally reconciling existing stoichiometric and topological approaches to network completion in a unified formalism. With it, we develop a hybrid ASP encoding and rely upon the theory reasoning capacities of the ASP system dingo for solving the resulting logic program with linear constraints over reals. We empirically evaluate our approach by means of the metabolic network of Escherichia coli. Our analysis shows that our novel approach yields greatly superior results than obtainable from purely qualitative or quantitative approaches.
KW  - answer set programming
KW  - metabolic network
KW  - gap-filling
KW  - linear programming
KW  - hybrid solving
KW  - bioinformatics
Y1  - 2018
U6  - https://doi.org/10.1017/S1471068418000455
SN  - 1471-0684
SN  - 1475-3081
VL  - 19
IS  - 1
SP  - 83
EP  - 108
PB  - Cambridge University Press
CY  - New York
ER  - 
TY  - JOUR
A1  - Dimopoulos, Yannis
A1  - Gebser, Martin
A1  - Lühne, Patrick
A1  - Romero Davila, Javier
A1  - Schaub, Torsten H.
T1  - plasp 3
BT  - Towards Effective ASP Planning
JF  - Theory and practice of logic programming
N2  - We describe the new version of the Planning Domain Definition Language (PDDL)-to-Answer Set Programming (ASP) translator plasp. First, it widens the range of accepted PDDL features. Second, it contains novel planning encodings, some inspired by Satisfiability Testing (SAT) planning and others exploiting ASP features such as well-foundedness. All of them are designed for handling multivalued fluents in order to capture both PDDL as well as SAS planning formats. Third, enabled by multishot ASP solving, it offers advanced planning algorithms also borrowed from SAT planning. As a result, plasp provides us with an ASP-based framework for studying a variety of planning techniques in a uniform setting. Finally, we demonstrate in an empirical analysis that these techniques have a significant impact on the performance of ASP planning.
KW  - knowledge representation and nonmonotonic reasoning
KW  - technical notes and rapid communications
KW  - answer set programming
KW  - automated planning
KW  - action and change
Y1  - 2019
U6  - https://doi.org/10.1017/S1471068418000583
SN  - 1471-0684
SN  - 1475-3081
VL  - 19
IS  - 3
SP  - 477
EP  - 504
PB  - Cambridge Univ. Press
CY  - New York
ER  - 
TY  - JOUR
A1  - Gebser, Martin
A1  - Obermeier, Philipp
A1  - Schaub, Torsten H.
A1  - Ratsch-Heitmann, Michel
A1  - Runge, Mario
T1  - Routing driverless transport vehicles in car assembly with answer set programming
JF  - Theory and practice of logic programming
N2  - Automated storage and retrieval systems are principal components of modern production and warehouse facilities. In particular, automated guided vehicles nowadays substitute human-operated pallet trucks in transporting production materials between storage locations and assembly stations. While low-level control systems take care of navigating such driverless vehicles along programmed routes and avoid collisions even under unforeseen circumstances, in the common case of multiple vehicles sharing the same operation area, the problem remains how to set up routes such that a collection of transport tasks is accomplished most effectively. We address this prevalent problem in the context of car assembly at Mercedes-Benz Ludwigsfelde GmbH, a large-scale producer of commercial vehicles, where routes for automated guided vehicles used in the production process have traditionally been hand-coded by human engineers. Such adhoc methods may suffice as long as a running production process remains in place, while any change in the factory layout or production targets necessitates tedious manual reconfiguration, not to mention the missing portability between different production plants. Unlike this, we propose a declarative approach based on Answer Set Programming to optimize the routes taken by automated guided vehicles for accomplishing transport tasks. The advantages include a transparent and executable problem formalization, provable optimality of routes relative to objective criteria, as well as elaboration tolerance towards particular factory layouts and production targets. Moreover, we demonstrate that our approach is efficient enough to deal with the transport tasks evolving in realistic production processes at the car factory of Mercedes-Benz Ludwigsfelde GmbH.
KW  - automated guided vehicle routing
KW  - car assembly operations
KW  - answer set programming
Y1  - 2018
U6  - https://doi.org/10.1017/S1471068418000182
SN  - 1471-0684
SN  - 1475-3081
VL  - 18
IS  - 3-4
SP  - 520
EP  - 534
PB  - Cambridge Univ. Press
CY  - New York
ER  - 
TY  - JOUR
A1  - Everardo Pérez, Flavio Omar
A1  - Osorio, Mauricio
T1  - Towards an answer set programming methodology for constructing programs following a semi-automatic approach
BT  - extended and revised version
JF  - Electronic notes in theoretical computer science
N2  - Answer Set Programming (ASP) is a successful rule-based formalism for modeling and solving knowledge-intense combinatorial (optimization) problems. Despite its success in both academic and industry, open challenges like automatic source code optimization, and software engineering remains. This is because a problem encoded into an ASP might not have the desired solving performance compared to an equivalent representation. Motivated by these two challenges, this paper has three main contributions. First, we propose a developing process towards a methodology to implement ASP programs, being faithful to existing methods. Second, we present ASP encodings that serve as the basis from the developing process. Third, we demonstrate the use of ASP to reverse the standard solving process. That is, knowing answer sets in advance, and desired strong equivalent properties, “we” exhaustively reconstruct ASP programs if they exist. This paper was originally motivated by the search of propositional formulas (if they exist) that represent the semantics of a new aggregate operator. Particularly, a parity aggregate. This aggregate comes as an improvement from the already existing parity (xor) constraints from xorro, where lacks expressiveness, even though these constraints fit perfectly for reasoning modes like sampling or model counting. To this end, this extended version covers the fundaments from parity constraints as well as the xorro system. Hence, we delve a little more in the examples and the proposed methodology over parity constraints. Finally, we discuss our results by showing the only representation available, that satisfies different properties from the classical logic xor operator, which is also consistent with the semantics of parity constraints from xorro.
KW  - answer set programming
KW  - combinatorial optimization problems
KW  - parity aggregate operator
Y1  - 2020
U6  - https://doi.org/10.1016/j.entcs.2020.10.004
SN  - 1571-0661
VL  - 354
SP  - 29
EP  - 44
PB  - Elsevier
CY  - Amsterdam [u.a.]
ER  -