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

Learning constraints through partial queries

ARTIFICIAL INTELLIGENCE 2023年 319卷

作者： Bessiere, Christian Carbonnel, Clement Dries, Anton Hebrard, Emmanuel Katsirelos, George Narodytska, Nina Quimper, Claude-Guy Stergiou, Kostas Tsouros, Dimosthenis C. Walsh, Toby Univ Montpellier CNRS Montpellier France Nokia Bell Labs Antwerp Belgium CNRS LAAS Toulouse France Univ Paris Saclay INRAE AgroParisTech UMR MIA Paris Saclay Gif Sur Yvette France Univ Fed Toulouse ANITI Toulouse France VMware Res Palo Alto CA USA Univ Laval Quebec City PQ Canada Univ Western Macedonia Kozani Greece Katholieke Univ Leuven Leuven Belgium UNSW Sydney Sydney Australia CSIRO Data61 Eveleigh NSW Australia

Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QuAcQ2, that, given a negative example, elucidates a constraint of the target network in a number of queries logarithmic in the size of the example. The whole constraint network can then be learned with a polynomial number of partial queries. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. We provide a version of QuAcQ2 with a cutoff mechanism that controls the time to generate a query. Our experiments illustrate the good behavior of QuAcQ2 in practice, especially in the case where QuAcQ2 is executed to learn the missing constraints in a partially filled constraint model. Our experiments also show that QuAcQ2 requires significantly fewer queries to learn a network than its predecessor QuAcQ1.(c) 2023 Elsevier B.V. All rights reserved.

关键词： constraint programming constraint acquisition Active learning

来源：评论

学校读者我要写书评

暂无评论

Automated streamliner portfolios for constraint satisfaction problems

引用

ARTIFICIAL INTELLIGENCE 2023年第1期319卷

作者： Spracklen, Patrick Dang, Nguyen Akgun, Ozgur Miguel, Ian Univ St Andrews Sch Comp Sci St Andrews KY16 9SX Fife Scotland

constraint programming (CP) is a powerful technique for solving large-scale combinatorial problems. Solving a problem proceeds in two distinct phases: modelling and solving. Effec-tive modelling has a huge impact on the performance of the solving process. Even with the advance of modern automated modelling tools, search spaces involved can be so vast that problems can still be difficult to solve. To further constrain the model, a more aggressive step that can be taken is the addition of streamliner constraints, which are not guaranteed to be sound but are designed to focus effort on a highly restricted but promising portion of the search space. Previously, producing effective streamlined models was a manual, difficult and time-consuming task. This paper presents a completely automated process to the gen-eration, search and selection of streamliner portfolios to produce a substantial reduction in search effort across a diverse range of problems. The results demonstrate a marked im-provement in performance for both Chuffed, a CP solver with clause learning, and lingeling, a modern SAT solver.(c) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： constraint programming constraint modelling constraint satisfaction problem Algorithm selection

来源：评论

学校读者我要写书评

暂无评论

Multi-level lot-sizing and job shop scheduling with lot-streaming: Reformulation and solution approaches

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 2023年第1期263卷

作者： Rohaninejad, Mohammad Hanzalek, Zdenek Czech Tech Univ Czech Inst Informat Robot & Cybernet Ind Informat Dept Prague 6 Czech Republic

This paper addresses a multi-level lot-sizing and job shop scheduling problem with lot-streaming. In the multi-level production system, workstations receive materials from the lower level, and after some operation, materials are shipped to the next level. Hence, establishing a material balance between the different levels is the most challenging part of multi-level production planning and scheduling. The material balance can be performed with or without lot-streaming. Lot-streaming effectively enables consecutive operations to overlap by splitting a processing lot into several sub-lots. In small-bucket time models, this capability is taken into account by establishing the material balance in each small unit of time (micro-period), which makes the models computationally expensive. In the present work, a novel and much less complicated big-bucket time formulation has been developed, which incorporates lot-streaming considering sequence-dependent setup times and capacitated machines. Computational experiments affirm the promising results of the proposed model compared to the well-known models in the literature. Moreover, two efficient heuristics have been developed for solving larger-size problems. First, the fix-and-relax algorithm as a constructive heuristic is combined with the fix-and-optimize algorithm as an improvement heuristic. Next, a decomposition heuristic is proposed using mixed-integer programming (MIP) and constraint programming (CP) in the master and sub-problem, respectively. The computational results show that the proposed heuristics are very efficient, even in solving large-sized problems.

关键词： Lot-sizing Job shop scheduling constraint programming Heuristic Fix and relax

来源：评论

学校读者我要写书评

暂无评论

Computing optimal hypertree decompositions with SAT

引用

ARTIFICIAL INTELLIGENCE 2023年 325卷

作者： Schidler, Andre Szeider, Stefan TU Wien Algorithms & Complex Grp Vienna Austria

Hypertree width is a prominent hypergraph invariant with many algorithmic applications in constraint satisfaction and databases. We propose two novel characterisations hypertree width in terms of linear orderings. We utilize these characterisations to obtain SAT, MaxSAT, and SMT encodings for computing the hypertree width exactly. We evaluate the encodings on an extensive set of benchmark instances and compare them to state-of-the-art exact methods for computing optimal hypertree width. Our results show that our approach outperforms these state-of-the-art algorithms.(c) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Hypertree width SAT SAT encoding MaxSAT SMT Optimization constraint programming

来源：评论

学校读者我要写书评

暂无评论

Solving complex problems using model transformations: from set constraint modeling to SAT instance solving

引用

EXPERT SYSTEMS WITH APPLICATIONS 2020年 149卷 113243-000页

作者： Lardeux, Frederic Monfroy, Eric Rodriguez-Tello, Eduardo Crawford, Broderick Soto, Ricardo Univ Angers LERIA 2 Blvd Lavoisier F-49045 Angers France Univ Nantes LS2N UMR 6004 2 Rue Houssiniere F-44322 Nantes France Cinvestav Tamaulipas Km 5-5 Carretera Victoria Soto La Marina Victoria Tamps 87130 Mexico Pontificia Univ Catolica Valparaiso Ave Brasil 2950 Valparaiso 2362807 Chile

On the one hand, solvers for the propositional satisfiability problem (SAT) can deal with huge instances composed of millions of variables and clauses. On the other hand, constraint Satisfaction Problems (CSP) can model problems as constraints over a set of variables with non-empty domains. They require combinatorial search methods as well as heuristics to be solved in a reasonable time. In this article, we present a technique that benefits from both expressive CSP modeling and efficient SAT solving. We model problems as CSP set constraints. Then, a propagation algorithm reduces the domains of variables by removing values that cannot participate in any valid assignment. The reduced CSP set constraints are transformed into a set of suitable SAT instances. They may be simplified by a preprocessing method before applying a standard SAT solver for computing their solutions. The practical usefulness of this technique is illustrated with two well-known problems: a) the Social Golfer, and b) the Sports Tournament Scheduling. We obtained competitive results either compared with ad hoc solvers or with hand-written SAT instances. Compared with direct SAT modeling, the proposed technique offers higher expressiveness, is less error-prone, and is relatively simpler to apply. The automatically generated propositional satisfiability instances are rather small in terms of clauses and variables. Hence, applying the constraint propagation phase, even huge instances of our problems can be tackled and efficiently solved. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： Model transformations constraint programming Set constraints SAT encoding Combinatorial problem

来源：评论

学校读者我要写书评

暂无评论

A comparative study of modeling and solution approaches for the multi-mode resource-constrained discrete time-cost trade-off problem: Case study of an ERP implementation project

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2022年第0期169卷

作者： Cakir, Gizem Subulan, Kemal Yildiz, Seyda Topaloglu Hamzadayi, Alper Asilkefeli, Ceren Dokuz Eylul Univ Grad Sch Nat & Appl Sci Izmir Turkey Dokuz Eylul Univ Fac Engn Dept Ind Engn Izmir Turkey Van Yuzuncu Yil Univ Dept Ind Engn Van Turkey

Most knowledge-intensive industries, especially companies developing software engineering projects such as Enterprise Resource Planning (ERP) implementation projects, generally necessitate finding the optimal trade-off between the project duration and total usage cost of the renewable resource costs (e.g., human resource expertise costs). Therefore, the MRC-DTCTP, which integrates classical multi-mode resource-constrained project scheduling (MRCPSP) and discrete time-cost trade-off problems (DTCTP), can be seen as a more applicable problem since it better reflects the objectives and requirements of today's real-life software project applications. The MRC-DTCTP is a much more complex variant of the MRCPSP since it aims to minimize total direct/indirect costs of the resources simultaneously under a pre-specified project deadline. Based on this motivation, a new explicit integer-linear programming (ILP) model of the MRC-DTCTP was first developed based on the implicit non-linear programming model of Wuliang and Chengen (2009). Due to its NP-hard nature, we also proposed a constraint programming (CP) model that includes several search strategies to solve large-sized problem instances within reasonable computation time. In addition, a genetic algorithm (GA) approach in combination with a Modified Serial Schedule Generation scheme (SSGS) is implemented to make further comparisons on several benchmark instances, which are generated based on the existing MRCPSP data sets taken from the project scheduling problem library (PSPLIB) by considering additional problem characteristics. A comprehensive experimental study has shown that the proposed CP model and GA approach can provide superior results in shorter run times for large-sized benchmark instances. Finally, an international Enterprise Resource Planning (ERP) Software Company's real-life application is presented. The ERP projects generally necessitate finding the optimal trade-off between project makespan and human resource

关键词： Multi-mode resource-constrained discrete time-cost tradeoff problem constraint programming Integer-linear programming Genetic algorithm ERP implementation projects

来源：评论

学校读者我要写书评

暂无评论

Logic-based Benders decomposition for the preemptive flexible job-shop scheduling problem

引用

COMPUTERS & OPERATIONS RESEARCH 2023年第1期152卷

作者： Juvin, Carla Houssin, Laurent Lopez, Pierre Univ Toulouse LAAS CNRS CNRS Toulouse France ISAE SUPAERO Toulouse France

In this paper, we focus on exact methods to solve the preemptive flexible job-shop scheduling problem with makespan minimisation objective function. Mathematical and constraint programming models enable the resolution of this problem for small instances. However, as an NP-hard problem, the cost of solving grows rapidly when considering larger instances. In this regard, we propose a logic-based Benders decomposition that relies on an efficient branch-and-bound procedure to solve the subproblem representing a pure (non-flexible) preemptive job-shop scheduling problem. Computational experiments are carried out and show the very good performance of our proposals.

关键词： Flexible job-shop scheduling Preemption Benders decomposition Mixed-integer programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

INTERFACE MODELING FOR QUALITY AND RESOURCE MANAGEMENT

引用

LOGICAL METHODS IN COMPUTER SCIENCE 2021年第2期17卷 19:1-19:34页

作者： Hendriks, Martijn Geilen, Marc Goossens, Kees de Jong, Rob Basten, Twan Eindhoven Univ Technol Eindhoven Netherlands ESI TNO Eindhoven Netherlands Philips Med Syst Int BV Best Netherlands

We develop an interface-modeling framework for quality and resource management that captures configurable working points of hardware and software components in terms of functionality, resource usage and provision, and quality indicators such as performance and energy consumption. We base these aspects on partially-ordered sets to capture quality levels, budget sizes, and functional compatibility. This makes the framework widely applicable and domain independent (although we aim for embedded and cyber-physical systems). The framework paves the way for dynamic (re-)configuration and multi-objective optimization of component-based systems for quality- and resource-management purposes.

关键词： constraint programming multi-objective combinatorial optimization Pareto algebra embedded and cyber-physical systems quality of service

来源：评论

学校读者我要写书评

暂无评论

Automatic generation of dominance breaking nogoods for a class of constraint optimization problems

引用

ARTIFICIAL INTELLIGENCE 2023年第1期323卷

作者： Lee, Jimmy H. M. Zhong, Allen Z. Chinese Univ Hong Kong Dept Comp Sci & Engineenng Shatin Hong Kong Peoples R China

constraint Optimization Problems (COPs) ask for an assignment of values to variables in order to optimize an objective subject to constraints that restrict the value combinations in the assignment. They are usually solved by the classical Branch and Bound (B & B) search algorithm. Dominance breaking is an important technique in B & B to prune assignments that are subordinate to others concerning the objective value and/or the satisfiability of constraints. In practice, the addition of constraints for dominance breaking can drastically speed up the B & B search for solving many COPs. However, identification of suboptimal assignments in COPs and derivation of useful constraints for dominance breaking are usually problem-specific and require sophisticated human insights on the problem *** paper proposes the first theoretical and practical framework for automatic generation of dominance breaking constraints for a class of COPs consisting of efficiently checkable objectives and constraints. In particular, the framework focuses on generating nogood constraints representing incompatible value assignments and formulates nogood generation as solving auxiliary constraint satisfaction problems. The proposed method can generate nogoods of varying strengths for dominance breaking by controlling the number of involved variables. Experimentation on various benchmarks demonstrates the effectiveness of the proposal in both efficiency and ease of use. The superior performance is also supported by a theoretical analysis to compare the relative strength of automatically generated nogoods with manually derived dominance breaking constraints in the literature. & COPY;2023 Elsevier B.V. All rights reserved.

关键词： Dominance breaking constraints constraint programming constraint optimization constraint satisfaction

来源：评论

学校读者我要写书评

暂无评论

Multi-criteria decision analysis for non-conformance diagnosis: A priority-based strategy combining data and business rules

引用

EXPERT SYSTEMS WITH APPLICATIONS 2021年 183卷 115212-115212页

作者： Ceballos, Rafael Borrego, Diana Teresa Gomez-Lopez, Maria Gasca, Rafael M. Univ Seville Dept Comp Sci Seville Spain

Business process analytics and verification have become a major challenge for companies, especially when process data is stored across different systems. It is important to ensure Business Process Compliance in both data-flow perspectives and business rules that govern the organisation. In the verification of data-flow accuracy, the conformance of data to business rules is a key element, since essential to fulfil policies and statements that govern corporate behaviour. The inclusion of business rules in an existing and already deployed process, which therefore already counts on stored data, requires the checking of business rules against data to guarantee compliance. If inconsistency is detected then the source of the problem should be determined, by discerning whether it is due to an erroneous rule or to erroneous data. To automate this, a diagnosis methodology following the incorporation of business rules is proposed, which simultaneously combines business rules and data produced during the execution of the company processes. Due to the high number of possible explanations of faults (data and/or business rules), the likelihood of faults has been included to propose an ordered list. In order to reduce these possibilities, we rely on the ranking calculated by means of an AHP (Analytic Hierarchy Process) and incorporate the experience described by users and/or experts. The methodology proposed is based on the constraint programming paradigm which is evaluated using a real example. .

关键词： Multi-criteria decision analysis Model-based diagnosis Analytic hierarchy process Business rule conformance constraint programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：