检索结果-内蒙古大学图书馆

logic-Based Benders Decomposition in Answer Set programming for Chronic Outpatients Scheduling

theory and practice of logic programming 2023年第4期23卷 848-864页

作者： Cappanera, Paola Gavanelli, Marco Nonato, Maddalena Roma, Marco Univ Firenze DINFO Florence Italy Univ Ferrara DE Ferrara Italy

In answer set programming (ASP), the user can define declaratively a problem and solve it with efficient solvers;practical applications of ASP are countless and several constraint problems have been successfully solved with ASP. On the other hand, solution time usually grows in a superlinear way (often, exponential) with respect to the size of the instance, which is impractical for large instances. A widely used approach is to split the optimization problem into subproblems (SPs) that are solved in sequence, some committing to the values assigned by others, and reconstructing a valid assignment for the whole problem by juxtaposing the solutions of the single SPs. On the one hand, this approach is much faster due to the superlinear behavior;on the other hand, it does not provide any guarantee of optimality: committing to the assignment of one SP can rule out the optimal solution from the search space. In other research areas, logic-Based Benders decomposition (LBBD) proved effective;in LBBD, the problem is decomposed into a master problem (MP) and one or several SPs. The solution of the MP is passed to the SPs that can possibly fail. In case of failure, a no-good is returned to the MP that is solved again with the addition of the new constraint. The solution process is iterated until a valid solution is obtained for all the SPs or the MP is proven infeasible. The obtained solution is provably optimal under very mild conditions. In this paper, we apply for the first time LBBD to ASP, exploiting an application in health care as case study. Experimental results show the effectiveness of the approach. We believe that the availability of LBBD can further increase the practical applicability of ASP technologies.

关键词： answer set programming logic-based Benders decomposition outpatients appointment scheduling chronic patients with comorbidities

来源：评论

学校读者我要写书评

暂无评论

Reasoning About Study Regulations in Answer Set programming

引用

theory and practice of logic programming 2024年第4期24卷 790-804页

作者： Hahn, Susana Schaub, Torsten Martens, Cedric Nemes, Amade Otunuya, Henry Romero, Javier Schellhorn, Sebastian Univ Potsdam Potsdam Germany Potassco Solut Potsdam Germany

We are interested in automating reasoning with and about study regulations, catering to various stakeholders, ranging from administrators, over faculty, to students at different stages. Our work builds on an extensive analysis of various study programs at the University of Potsdam. The conceptualization of the underlying principles provides us with a formal account of study regulations. In particular, the formalization reveals the properties of admissible study plans. With these at end, we propose an encoding of study regulations in Answer Set programming that produces corresponding study plans. Finally, we show how this approach can be extended to a generic user interface for exploring study plans.

关键词： answer set programming study regulations and plans

来源：评论

学校读者我要写书评

暂无评论

Answering Fuzzy Queries over Fuzzy DL-Lite Ontologies

引用

theory and practice of logic programming 2023年第3期23卷 594-623页

作者： Pasi, Gabriella Penaloza, Rafael Univ Milano Bicocca Milan Italy

A prominent problem in knowledge representation is how to answer queries taking into account also the implicit consequences of an ontology representing domain knowledge. While this problem has been widely studied within the realm of description logic ontologies, it has been surprisingly neglected within the context of vague or imprecise knowledge, particularly from the point of view of mathematical fuzzy logic. In this paper, we study the problem of answering conjunctive queries and threshold queries w.r.t. ontologies in fuzzy DL-Lite. Specifically, we show through a rewriting approach that threshold query answering w.r.t. consistent ontologies remains in AC(0) in data complexity, but that conjunctive query answering is highly dependent on the selected triangular norm, which has an impact on the underlying semantics. For the idempotent Godel t-norm, we provide an effective method based on a reduction to the classical case.

关键词： fuzzy description logics query answering DL-Lite mathematical fuzzy logic

来源：评论

学校读者我要写书评

暂无评论

Answer-Set programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling

引用

theory and practice of logic programming 2023年第6期23卷 1281-1306页

作者： Eiter, Thomas Geibinger, Tobias Musliu, Nysret Oetsch, Johannes Skocovsky, Peter Stepanova, Daria Vienna Univ Technol TU Wien Inst L & Computat Vienna Austria Robert Bosch Campus 1 D-71272 Renningen Germany

We deal with a challenging scheduling problem on parallel machines with sequence-dependent setup times and release dates from a real-world application of semiconductor work-shop production. There, jobs can only be processed by dedicated machines, thus few machines can determine the makespan almost regardless of how jobs are scheduled on the remaining ones. This causes problems when machines fail and jobs need to be rescheduled. Instead of optimising only the makespan, we put the individual machine spans in non-ascending order and lexicographically minimise the resulting tuples. This achieves that all machines complete as early as possible and increases the robustness of the schedule. We study the application of answer-set programming (ASP) to solve this problem. While ASP eases modelling, the combination of timing constraints and the considered objective function challenges current solving technology. The former issue is addressed by using an extension of ASP by difference logic. For the latter, we devise different algorithms that use multi-shot solving. To tackle industrial-sized instances, we study different approximations and heuristics. Our experimental results show that ASP is indeed a promising knowledge representation and reasoning (KRR) paradigm for this problem and is competitive with state-of-the-art constraint programming (CP) and Mixed-Integer programming (MIP) solvers.

关键词： answer-set programming parallel machine scheduling lexicographical optimisation

来源：评论

学校读者我要写书评

暂无评论

How to Build Your Own ASP-based System?!

引用

theory and practice of logic programming 2023年第1期23卷 299-361页

作者： Kaminski, Roland Romero, Javier Schaub, Torsten Wanko, Philipp Univ Potsdam Potsdam Germany

Answer Set programming, or ASP for short, has become a popular and sophisticated approach to declarative problem solving. Its popularity is due to its attractive modeling-grounding-solving workflow that provides an easy approach to problem solving, even for laypersons outside computer science. However, in contrast to ASP's ease of use, the high degree of sophistication of the underlying technology makes it even hard for ASP experts to put ideas into practice whenever this involves modifying ASP's machinery. For addressing this issue, this tutorial aims at enabling users to build their own ASP-based systems. More precisely, we show how the ASP system clingo can be used for extending ASP and for implementing customized special-purpose systems. To this end, we propose two alternatives. We begin with a traditional AI technique and show how metaprogramming can be used for extending ASP. This is a rather light approach that relies on clingo's reification feature to use ASP itself for expressing new functionalities. The second part of this tutorial uses traditional programming (in Python) for manipulating clingo via its application programming interface. This approach allows for changing and controlling the entire model-ground-solve workflow of ASP. Central to this is clingo's new Application class that allows us to draw on clingo's infrastructure by customizing processes similar to the one in clingo. For instance, we may apply manipulations to programs' abstract syntax trees, control various forms of multi-shot solving, and set up theory propagators for foreign inferences. A cross-sectional structure, spanning meta as well as application programming, is clingo's intermediate format, aspif, that specifies the interface among the underlying grounder and solver. We illustrate the aforementioned concepts and techniques throughout this tutorial by means of examples and several nontrivial case studies. In particular, we show how clingo can be extended by difference constraints

关键词： Answer Set programming Answer Set Systems Meta programming Answer Set Solving modulo Theories

来源：评论

学校读者我要写书评

暂无评论

On the Configuration of More and Less Expressive logic Programs

引用

theory and practice of logic programming 2023年第2期23卷 415-443页

作者： Dodaro, Carmine Maratea, Marco Vallati, Mauro Univ Calabria Arcavacata Di Rende Italy Univ Genoa Genoa Italy Univ Huddersfield Huddersfield HD1 3DH W Yorkshire England

The decoupling between the representation of a certain problem, that is, its knowledge model, and the reasoning side is one of main strong points of model-based artificial intelligence (AI). This allows, for example, to focus on improving the reasoning side by having advantages on the whole solving process. Further, it is also well known that many solvers are very sensitive to even syntactic changes in the input. In this paper, we focus on improving the reasoning side by taking advantages of such sensitivity. We consider two well-known model-based AI methodologies, SAT and ASP, define a number of syntactic features that may characterise their inputs, and use automated configuration tools to reformulate the input formula or program. Results of a wide experimental analysis involving SAT and ASP domains, taken from respective competitions, show the different advantages that can be obtained by using input reformulation and configuration.

关键词： SATisfiability answer set programming knowledge configuration

来源：评论

学校读者我要写书评

暂无评论

programming with Dependent Additive Pairs 25th

Programming with Dependent Additive Pairs

引用

25th International Symposium on Trends in Functional programming

作者： Sefl, Vit Charles Univ Prague Prague Czech Republic

ISBN: (纸本)9783031745577;9783031745584

Linear logic gives us additive pairs in the form of the additive conjunction. Intuitionistic type theory gives us dependent pairs in the form of the dependent sum type. What happens when we combine these two kinds of pairs together? And is this new pair type useful in practice? To answer these questions, we employ quantitative type theory, which can describe both substructural and dependent types simultaneously. In our previous work, we introduced dependent additive pairs. In this work, we show how these pairs can be used in three completely different scenarios: folding data structures using linear recursion schemes, computing resource-aware proofs, and defining additive versions of inductive and coinductive types. Each of these scenarios is then illustrated by an implementation in the Janus language.

关键词： Dependent types Linear types Quantitative type theory Additive pairs

来源：评论

学校读者我要写书评

暂无评论

Declarative Approaches to Counterfactual Explanations for Classification

引用

theory and practice of logic programming 2023年第3期23卷 559-593页

作者： Bertossi, Leopoldo Univ Adolfo Ibanez Fac Engn & Sci Santiago Chile Millennium Inst Fdn Res Data IMFD Santiago Chile

We propose answer-set programs that specify and compute counterfactual interventions on entities that are input on a classification model. In relation to the outcome of the model, the resulting counterfactual entities serve as a basis for the definition and computation of causality-based explanation scores for the feature values in the entity under classification, namely responsibility scores. The approach and the programs can be applied with black-box models, and also with models that can be specified as logic programs, such as rule-based classifiers. The main focus of this study is on the specification and computation of best counterfactual entities, that is, those that lead to maximum responsibility scores. From them one can read off the explanations as maximum responsibility feature values in the original entity. We also extend the programs to bring into the picture semantic or domain knowledge. We show how the approach could be extended by means of probabilistic methods, and how the underlying probability distributions could be modified through the use of constraints. Several examples of programs written in the syntax of the DLV ASP-solver, and run with it, are shown.

关键词： classification explanations counterfactuals causality answer-set programming constraints

来源：评论

学校读者我要写书评

暂无评论

Constraint Answer Set programming: Integrational and Translational (or SMT-based) Approaches

引用

theory and practice of logic programming 2023年第1期23卷 195-225页

作者： Lierler, Yuliya Univ Nebraska Omaha NE 68182 USA

Constraint answer set programming or CASP, for short, is a hybrid approach in automated reasoning putting together the advances of distinct research areas such as answer set programming, constraint processing, and satisfiability modulo theories. CASP demonstrates promising results, including the development of a multitude of solvers: acsolver, clingcon, ezcsp, idp, inca, dingo, mingo, aspmt2smt, clingo[l,dl], and ezsmt. It opens new horizons for declarative programming applications such as solving complex train scheduling problems. Systems designed to find solutions to constraint answer set programs can be grouped according to their construction into, what we call, integrational or translational approaches. The focus of this paper is an overview of the key ingredients of the design of constraint answer set solvers drawing distinctions and parallels between integrational and translational approaches. The paper also provides a glimpse at the kind of programs its users develop by utilizing a CASP encoding of Traveling Salesman problem for illustration. In addition, we place the CASP technology on the map among its automated reasoning peers as well as discuss future possibilities for the development of CASP.

关键词： answer set programming constraints satisfiability modulo theories

来源：评论

学校读者我要写书评

暂无评论

Strong Equivalence of logic Programs with Counting

引用

theory and practice of logic programming 2022年第4期22卷 573-588页

作者： Lifschitz, Vladimir Univ Texas Austin Austin TX 78712 USA

In answer set programming, two groups of rules are considered strongly equivalent if they have the same meaning in any context. In some cases, strong equivalence of programs in the input language of the grounder gringo can be established by deriving rules of each program from rules of the other. The possibility of such proofs has been demonstrated for a subset of that language that includes comparisons, arithmetic operations, and simple choice rules, but not aggregates. This method is extended here to a class of programs in which some uses of the #count aggregate are allowed.

关键词： aggregates answer set programming strong equivalence

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：