TY - JOUR A1 - Abseher, Michael A1 - Musliu, Nysret A1 - Woltran, Stefan A1 - Gebser, Martin A1 - Schaub, Torsten H. T1 - Shift Design with Answer Set Programming JF - Fundamenta informaticae N2 - Answer Set Programming (ASP) is a powerful declarative programming paradigm that has been successfully applied to many different domains. Recently, ASP has also proved successful for hard optimization problems like course timetabling and travel allotment. In this paper, we approach another important task, namely, the shift design problem, aiming at an alignment of a minimum number of shifts in order to meet required numbers of employees (which typically vary for different time periods) in such a way that over- and understaffing is minimized. We provide an ASP encoding of the shift design problem, which, to the best of our knowledge, has not been addressed by ASP yet. Our experimental results demonstrate that ASP is capable of improving the best known solutions to some benchmark problems. Other instances remain challenging and make the shift design problem an interesting benchmark for ASP-based optimization methods. Y1 - 2016 U6 - https://doi.org/10.3233/FI-2016-1396 SN - 0169-2968 SN - 1875-8681 VL - 147 SP - 1 EP - 25 PB - IOS Press CY - Amsterdam ER - TY - JOUR A1 - Gebser, Martin A1 - Schaub, Torsten H. T1 - Modeling and Language Extensions JF - AI magazine N2 - Answer set programming (ASP) has emerged as an approach to declarative problem solving based on the stable model semantics for logic programs. The basic idea is to represent a computational problem by a logic program, formulating constraints in terms of rules, such that its answer sets correspond to problem solutions. To this end, ASP combines an expressive language for high-level modeling with powerful low-level reasoning capacities, provided by off-the-shelf tools. Compact problem representations take advantage of genuine modeling features of ASP, including (first-order) variables, negation by default, and recursion. In this article, we demonstrate the ASP methodology on two example scenarios, illustrating basic as well as advanced modeling and solving concepts. We also discuss mechanisms to represent and implement extended kinds of preferences and optimization. An overview of further available extensions concludes the article. Y1 - 2016 SN - 0738-4602 VL - 37 SP - 33 EP - 44 PB - Association for the Advancement of Artificial Intelligence CY - Menlo Park ER - TY - JOUR A1 - Kaufmann, Benjamin A1 - Leone, Nicola A1 - Perri, Simona A1 - Schaub, Torsten H. T1 - Grounding and Solving in Answer Set Programming JF - AI magazine N2 - Answer set programming is a declarative problem-solving paradigm that rests upon a work flow involving modeling, grounding, and solving. While the former is described by Gebser and Schaub (2016), we focus here on key issues in grounding, or how to systematically replace object variables by ground terms in an effective way, and solving, or how to compute the answer sets, of a propositional logic program obtained by grounding. Y1 - 2016 SN - 0738-4602 VL - 37 SP - 25 EP - 32 PB - Association for the Advancement of Artificial Intelligence CY - Menlo Park ER - TY - JOUR A1 - Ostrowski, Max A1 - Pauleve, L. A1 - Schaub, Torsten H. A1 - Siegel, A. A1 - Guziolowski, Carito T1 - Boolean network identification from perturbation time series data combining dynamics abstraction and logic programming JF - Biosystems : journal of biological and information processing sciences N2 - Boolean networks (and more general logic models) are useful frameworks to study signal transduction across multiple pathways. Logic models can be learned from a prior knowledge network structure and multiplex phosphoproteomics data. However, most efficient and scalable training methods focus on the comparison of two time-points and assume that the system has reached an early steady state. In this paper, we generalize such a learning procedure to take into account the time series traces of phosphoproteomics data in order to discriminate Boolean networks according to their transient dynamics. To that end, we identify a necessary condition that must be satisfied by the dynamics of a Boolean network to be consistent with a discretized time series trace. Based on this condition, we use Answer Set Programming to compute an over-approximation of the set of Boolean networks which fit best with experimental data and provide the corresponding encodings. Combined with model-checking approaches, we end up with a global learning algorithm. Our approach is able to learn logic models with a true positive rate higher than 78% in two case studies of mammalian signaling networks; for a larger case study, our method provides optimal answers after 7 min of computation. We quantified the gain in our method predictions precision compared to learning approaches based on static data. Finally, as an application, our method proposes erroneous time-points in the time series data with respect to the optimal learned logic models. (C) 2016 Elsevier Ireland Ltd. All rights reserved. KW - Model identification KW - Time series data KW - Multiplex phosphoproteomics data KW - Boolean networks KW - Answer Set Programming Y1 - 2016 U6 - https://doi.org/10.1016/j.biosystems.2016.07.009 SN - 0303-2647 SN - 1872-8324 VL - 149 SP - 139 EP - 153 PB - Elsevier CY - Oxford ER - TY - JOUR A1 - Bomanson, Jori A1 - Janhunen, Tomi A1 - Schaub, Torsten H. A1 - Gebser, Martin A1 - Kaufmann, Benjamin T1 - Answer Set Programming Modulo Acyclicity JF - Fundamenta informaticae N2 - Acyclicity constraints are prevalent in knowledge representation and applications where acyclic data structures such as DAGs and trees play a role. Recently, such constraints have been considered in the satisfiability modulo theories (SMT) framework, and in this paper we carry out an analogous extension to the answer set programming (ASP) paradigm. The resulting formalism, ASP modulo acyclicity, offers a rich set of primitives to express constraints related to recursive structures. In the technical results of the paper, we relate the new generalization with standard ASP by showing (i) how acyclicity extensions translate into normal rules, (ii) how weight constraint programs can be instrumented by acyclicity extensions to capture stability in analogy to unfounded set checking, and (iii) how the gap between supported and stable models is effectively closed in the presence of such an extension. Moreover, we present an efficient implementation of acyclicity constraints by incorporating a respective propagator into the state-of-the-art ASP solver CLASP. The implementation provides a unique combination of traditional unfounded set checking with acyclicity propagation. In the experimental part, we evaluate the interplay of these orthogonal checks by equipping logic programs with supplementary acyclicity constraints. The performance results show that native support for acyclicity constraints is a worthwhile addition, furnishing a complementary modeling construct in ASP itself as well as effective means for translation-based ASP solving. Y1 - 2016 U6 - https://doi.org/10.3233/FI-2016-1398 SN - 0169-2968 SN - 1875-8681 VL - 147 SP - 63 EP - 91 PB - IOS Press CY - Amsterdam ER -