The Operating Room Scheduling (ORS) problem deals with the optimization of daily operating room surgery schedules. It is a challenging problem subject to many constraints, like to determine the starting time of differ...
详细信息
The Operating Room Scheduling (ORS) problem deals with the optimization of daily operating room surgery schedules. It is a challenging problem subject to many constraints, like to determine the starting time of different surgeries and allocating the required resources, including the availability of beds in different units. In the past years, answer set programming (ASP) has been successfully employed for addressing and solving the ORS problem. Despite its importance, due to the inherent difficulty of retrieving real data, all the analyses on ORS ASP encodings have been performed on synthetic data so far. In this paper, first we present a new, improved ASP encoding for the ORS problem. Then, we deal with the real case of ASL1 Liguria, an Italian health authority operating through three hospitals, and present adaptations of the ASP encodings to deal with the real-world data. Further, we analyse the resulting encodings on hospital scheduling data by ASL1 Liguria. Results on some scenarios show that the ASP solutions produce satisfying schedules also when applied to such challenging, real data.
The problem of scheduling pre-operative assessment clinic (PAC) consists of assigning patients to a day for the exams needed before a surgical procedure, taking into account patients with different priority levels, du...
详细信息
The problem of scheduling pre-operative assessment clinic (PAC) consists of assigning patients to a day for the exams needed before a surgical procedure, taking into account patients with different priority levels, due dates and operators availability. Realizing a satisfying schedule is of upmost importance for a hospital, since delay in PAC can cause delay in the subsequent phases, thus lowering patients' satisfaction. In this paper, we propose a two-phase solution to the PAC problem: in the first phase, patients are assigned to a day taking into account a default list of exams;then, in the second phase, having the actual list of exams needed by each patient, we use the results of the first phase to assign a starting time to each exam. We first present a mathematical formulation for both problems. Further, we present a solution where modeling and solving are done via answer set programming. We then introduce a rescheduling solution that may come into play when the scheduling solution cannot be applied fully. Experiments employing synthetic benchmarks on both scheduling and rescheduling show that both solutions provide satisfying results in short time. We finally show the implementation and usage of a web application that allows to run our scheduling solution and analyze the results graphically in a transparent way.
We provide a comprehensive elaboration of the theoretical foundations of variable instantiation, or grounding, in answer set programming (ASP). Building on the semantics of ASP's modeling language, we introduce a ...
详细信息
We provide a comprehensive elaboration of the theoretical foundations of variable instantiation, or grounding, in answer set programming (ASP). Building on the semantics of ASP's modeling language, we introduce a formal characterization of grounding algorithms in terms of (fixed point) operators. A major role is played by dedicated well-founded operators whose associated models provide semantic guidance for delineating the result of grounding along with on-the-fly simplifications. We address an expressive class of logic programs that incorporates recursive aggregates and thus amounts to the scope of existing ASP modeling languages. This is accompanied with a plain algorithmic framework detailing the grounding of recursive aggregates. The given algorithms correspond essentially to the ones used in the ASP grounder gringo.
State-of-the-art answer set programming (ASP) solvers rely on a program called a grounder to convert non-ground programs containing variables into variable-free, propositional programs. The size of this grounding depe...
详细信息
State-of-the-art answer set programming (ASP) solvers rely on a program called a grounder to convert non-ground programs containing variables into variable-free, propositional programs. The size of this grounding depends heavily on the size of the non-ground rules, and thus, reducing the size of such rules is a promising approach to improve solving performance. To this end, in this paper we announce 1popt, a tool that decomposes large logic programming rules into smaller rules that are easier to handle for current solvers. The tool is specifically tailored to handle the standard syntax of the ASP language (ASP-Core) and makes it easier for users to write efficient and intuitive ASP programs, which would otherwise often require significant handtuning by expert ASP engineers. It is based on an idea proposed by Morak and Woltran (2012) that we extend significantly in order to handle the full ASP syntax, including complex constructs like aggregates, weak constraints, and arithmetic expressions. We present the algorithm, the theoretical foundations on how to treat these constructs, as well as an experimental evaluation showing the viability of our approach.
answer set programming (ASP) is a form of declarative programming that allows to succinctly formulate and efficiently solve complex problems. An intuitive extension of this formalism is communicating ASP, in which mul...
详细信息
answer set programming (ASP) is a form of declarative programming that allows to succinctly formulate and efficiently solve complex problems. An intuitive extension of this formalism is communicating ASP, in which multiple ASP programs collaborate to solve the problem at hand. However, the expressiveness of communicating ASP has not been thoroughly studied. In this paper, we present a systematic study of the additional expressiveness offered by allowing ASP programs to communicate. First, we consider a simple form of communication where programs are only allowed to ask questions to each other. For the most part, we deliberately consider only simple programs, i.e. programs for which computing the answersets is in P. We find that the problem of deciding whether a literal is in some answerset of a communicating ASP program using simple communication is NP-hard. In other words, due to the ability of these simple ASP programs to communicate and collaborate, we move up a step in the polynomial hierarchy. Second, we modify the communication mechanism to also allow us to focus on a sequence of communicating programs, where each program in the sequence may successively remove some of the remaining models. This mimics a network of leaders, where the first leader has the first say and may remove models that he or she finds unsatisfactory. Using this particular communication mechanism allows us to capture the entire polynomial hierarchy. This means, in particular, that communicating ASP could be used to solve problems that are above the second level of polynomial hierarchy, such as some forms of abductive reasoning as well as PSPACE-complete problems such as STRIPS planning.
A common feature in answer set programming is the use of a second negation, stronger than default negation and sometimes called explicit, strong or classical negation. This explicit negation is normally used in front ...
详细信息
A common feature in answer set programming is the use of a second negation, stronger than default negation and sometimes called explicit, strong or classical negation. This explicit negation is normally used in front of atoms, rather than allowing its use as a regular operator. In this paper we consider the arbitrary combination of explicit negation with nested expressions, as those defined by Lifschitz, Tang and Turner. We extend the concept of reduct for this new syntax and then prove that it can be captured by an extension of Equilibrium Logic with this second negation. We study some properties of this variant and compare to the already known combination of Equilibrium Logic with Nelson's strong negation.
We propose a combination of logic programming under the answerset semantics with the description logics SHIF(D) and SHOIN(D), which underly the Web ontology languages OWL Lite and OWL DL, respectively. To this end, w...
详细信息
We propose a combination of logic programming under the answerset semantics with the description logics SHIF(D) and SHOIN(D), which underly the Web ontology languages OWL Lite and OWL DL, respectively. To this end, we introduce description logic programs (or di-programs), which consist of a description logic knowledge base L and a finite set P of description logic rules (or dl-rules). Such rules are similar to usual rules in nonmonotonic logic programs, but they may also contain queries to L, possibly under default negation, in their bodies. They allow for building rules on top of ontologies but also, to a limited extent, building ontologies on top of rules. We define a suite of semantics for various classes of dl-programs, which conservatively extend the standard semantics of the respective classes and coincide with it in absence of a description logic knowledge base. More concretely, we generalize positive, stratified, and arbitrary normal logic programs to dl-programs, and define a Herbrand model semantics for them. We show that they have similar properties as ordinary logic programs, and also provide fixpoint characterizations in terms of (iterated) consequence operators. For arbitrary dl-programs, we define answersets by generalizing Gelfond and Lifschitz's notion of a transform, leading to a strong and a weak answerset semantics, which are based on reductions to the semantics of positive dl-programs and ordinary positive logic programs, respectively. We also show how the weak answersets can be computed utilizing answersets of ordinary normal logic programs. Furthermore, we show how some advanced reasoning tasks for the Semantic Web, including different forms of closed-world reasoning and default reasoning, as well as DL-safe rules, can be realized on top of dl-programs. Finally, we give a precise picture of the computational complexity of dl-programs, and we describe efficient algorithms and a prototype implementation of dl-programs which is available on
With the increasing adoption of role-based access control (RBAC) in business security, role mining technology has been widely applied to aid the process of migrating a non-RBAC system to an RBAC system. However, becau...
详细信息
With the increasing adoption of role-based access control (RBAC) in business security, role mining technology has been widely applied to aid the process of migrating a non-RBAC system to an RBAC system. However, because it is hard to deal with a variety of constraint conflicts at the same time, none of existing role mining algorithms can simultaneously satisfy various constraints that usually describe organizations' security and business requirements. To extend the ability of role mining technology, this paper proposes a novel role mining approach using answer set programming (ASP) that complies with constraints and meets various optimization objectives, named constrained role miner (CRM). Essentially, the idea is that ASP is an approach to declarative problem solving. Thus, either to discover RBAC configurations or to deal with conflicts between constraints, ASP programs do not need to specify how answers are computed. Finally, we demonstrate the effectiveness and efficiency of our approach through experimental results. (C) 2014 Elsevier B.V. All rights reserved.
Background: The impact of a perturbation, over-expression, or repression of a key node on an organism, can be modelled based on a regulatory and/or metabolic network. Integration of these two networks could improve ou...
详细信息
Background: The impact of a perturbation, over-expression, or repression of a key node on an organism, can be modelled based on a regulatory and/or metabolic network. Integration of these two networks could improve our global understanding of biological mechanisms triggered by a perturbation. This study focuses on improving the modelling of the regulatory network to facilitate a possible integration with the metabolic network. Previously proposed methods that study this problem fail to deal with a real-size regulatory network, computing predictions sensitive to perturbation and quantifying the predicted species behaviour more ***: To address previously mentioned limitations, we develop a new method based on answer set programming, MajS. It takes a regulatory network and a discrete partial set of observations as input. MajS tests the consistency between the input data, proposes minimal repairs on the network to establish consistency, and finally computes weighted and signed predictions over the network species. We tested MajS by comparing the HIF-1 signalling pathway with two gene-expression datasets. Our results show that MajS can predict 100% of unobserved species. When comparing MajS with two similar (discrete and quantitative) tools, we observed that compared with the discrete tool, MajS proposes a better coverage of the unobserved species, is more sensitive to system perturbations, and proposes predictions closer to real data. Compared to the quantitative tool, MajS provides more refined discrete predictions that agree with the dynamic proposed by the quantitative ***: MajS is a new method to test the consistency between a regulatory network and a dataset that provides computational predictions on unobserved network species. It provides fine-grained discrete predictions by outputting the weight of the predicted sign as a piece of additional information. MajS' output, thanks to its weight, could easily be integrated with metabolic network
In this paper, we define a class of nested logic programs, called Nested Logic Programs with Ordered Disjunction (LPODs(+)), which makes it possible to specify conditional (qualitative) preferences by means of nested ...
详细信息
In this paper, we define a class of nested logic programs, called Nested Logic Programs with Ordered Disjunction (LPODs(+)), which makes it possible to specify conditional (qualitative) preferences by means of nested preference statements. To this end, we augment the syntax of Logic Programs with Ordered Disjunction (LPODs) to capture more general expressions. We define the LPODs(+) semantics in a simple way and we extend most of the results of LPODs showing how our approach generalizes the LPODs framework in a proper way. We also show how the LPODs(+) semantics can be computed in terms of a translation procedure that maps a nested ordered disjunction program (OD+-program) into a disjunctive logic program.
暂无评论