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

33rd International Conference on Logic programming / 23rd International Conference on Principles and Practice of constraint programming (CP) / 20th International Conference on Theory and Applications of Satisfiability Testing (SAT)

作者： Chabert, Maxime Solnon, Christine Univ Lyon INSA Lyon LIRIS F-69622 Villeurbanne France Infologic Bourg Les Valence France

ISBN: (纸本)9783319661582;9783319661575

A conceptual clustering is a set of formal concepts (i.e., closed itemsets) that defines a partition of a set of transactions. Finding a conceptual clustering is an NP-complete problem for which constraint programming (CP) and Integer Linear programming (ILP) approaches have been recently proposed. We introduce new CP models to solve this problem: a pure CP model that uses set constraints, and an hybrid model that uses a data mining tool to extract formal concepts in a preprocessing step and then uses CP to select a subset of formal concepts that defines a partition. We compare our new models with recent CP and ILP approaches on classical machine learning instances. We also introduce a new set of instances coming from a real application case, which aims at extracting setting concepts from an Enterprise Resource Planning (ERP) software. We consider two classic criteria to optimize, i.e., the frequency and the size. We show that these criteria lead to extreme solutions with either very few small formal concepts or many large formal concepts, and that compromise clusterings may be obtained by computing the Pareto front of non dominated clusterings.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

constraint programming Applied to the Multi-Skill Project Scheduling Problem 23rd

Constraint Programming Applied to the Multi-Skill Project Sc...

引用

作者： Young, Kenneth D. Feydy, Thibaut Schutt, Andreas Univ Melbourne Melbourne Vic Australia CSIRO Decis Sci Data61 Melbourne Vic Australia

ISBN: (纸本)9783319661582;9783319661575

The Multi-Skill Project Scheduling Problem is a variant of the well-studied Resource Constrained Project Scheduling Problem, in which the resources are assumed to be multi-skilled. Practical applications of this problem occur when the resources considered are a multi-skilled workforce or multi-purpose machines. This variant introduces a set of assignment decisions between the resources and activities, further to the usual scheduling decisions. This additional layer of complexity results in the problem becoming far more difficult to solve. We investigate different constraint programming models and searches tailored for solvers with nogood learning. These models and searches are then evaluated on instances available from the literature as well as newly generated ones. Using the best performing model and search, we are able to close at least 87 open instances from the literature.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

Automated Generation of Business Process Models using constraint Logic programming in Python

Automated Generation of Business Process Models using Constr...

引用

Federated Conference on Computer Science and Information Systems (FedCSIS)

作者： Paszun, Tymoteusz Wisniewski, Piotr Kluza, Krzysztof Ligeza, Antoni AGH Univ Sci & Technol Al A Mickiewicza 30 PL-30059 Krakow Poland

ISBN: (纸本)9788395235788

High complexity of business processes in real-life organizations is a constantly rising issue. In consequence, modeling a workflow is a challenge for process stakeholders. Yet, to facilitate this task, new methods can be implemented to automate the phase of process design. As a main contribution of this paper, we propose an approach to generate process models based on activities performed by the participants, where the exact order of execution does not need to he specified. Nevertheless, the goal of our method is to generate artificial workflow traces of a process using constraint programming and a set of predefined rules. As a final step, the approach was implemented as a dedicated tool and evaluated on a set of test examples that prove that our method is capable of creating correct process models.

关键词： business process management process composition workflow logs constraint programming BPMN

来源：评论

学校读者我要写书评

暂无评论

A constraint programming approach for the team orienteering problem with time windows

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2017年 107卷 178-195页

作者： Gedik, Ridvan Kirac, Emre Milburn, Ashlea Bennet Rainwater, Chase Univ New Haven Dept Mech & Ind Engn 300 Boston Post Rd West Haven CT 06516 USA Univ Houston Clear Lake Dept Engn 2700 Bay Area Blvd Houston TX 77058 USA Univ Arkansas Dept Ind Engn 4207 Bell Engn Ctr1 Univ Arkansas Fayetteville AR 72701 USA

The team orienteering problem with time windows (TOPTW) is a NP-hard combinatorial optimization problem. It has many real-world applications, for example, routing technicians and disaster relief routing. In the TOPTW, a set of locations is given. For each, the profit, service time and time window are known. A fleet of homogenous vehicles are available for visiting locations and collecting their associated profits. Each vehicle is constrained by a maximum tour duration. The problem is to plan a set of vehicle routes that begin and end at a depot, visit each location no more than once by incorporating time window constraints. The objective is to maximize the profit collected. In this study we discuss how to use constraint programming (CP) to formulate and solve TOPTW by applying interval variables, global constraints and domain filtering algorithms. We propose a CP model and two branching strategies for the TOPTW. The approach finds 119 of the best-known solutions for 304 TOPTW benchmark instances from the literature. Moreover, the proposed method finds one new best-known solution for TOPTW benchmark instances and proves the optimality of the best-known solutions for two additional instances. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Team orienteering problem Time windows Vehicle routing constraint programming Interval variable

来源：评论

学校读者我要写书评

暂无评论

Mining Time-constrained Sequential Patterns with constraint programming

引用

constraintS 2017年第4期22卷 548-570页

作者： Aoga, John O. R. Guns, Tias Schaus, Pierre Univ Catholique Louvain UCLouvain Inst Informat & Commun Technol Elect & Appl Math Louvain Belgium UAC Ecole Doctorale Sci Ingn ED SDI Calavi Benin Vrije Univ Brussel Brussels Belgium Katholieke Univ Leuven Leuven Belgium

constraint programming (CP) has proven to be an effective platform for constraint based sequence mining. Previous work has focused on standard frequent sequence mining, as well as frequent sequence mining with a maximum 'gap' between two matching events in a sequence. The main challenge in the latter is that this constraint can not be imposed independently of the omnipresent frequency constraint. Indeed, the gap constraint changes whether a subsequence is included in a sequence, and hence its frequency. In this work, we go beyond that and investigate the integration of timed events and constraining the minimum/maximum gap as well as minimum/maximum span. The latter constrains the allowed time between the first and last matching event of a pattern. We show how the three are interrelated, and what the required changes to the frequency constraint are. Key in our approach is the concept of an extension window defined by gap/span and we develop techniques to avoid scanning the sequences needlessly, as well as using a backtracking-aware data structure. Experiments demonstrate that the proposed approach outperforms both specialized and CP-based approaches in almost all cases and that the advantage increases as the minimum frequency threshold decreases. This paper is an extension of the original manuscript presented at CPAIOR'17 [5].

关键词： Data mining Sequential pattern mining constraint programming Global constraint Gap constraint Span constraint Time constraint

来源：评论

学校读者我要写书评

暂无评论

Constrained clustering by constraint programming

引用

ARTIFICIAL INTELLIGENCE 2017年 244卷 70-94页

作者： Thi-Bich-Hanh Dao Khanh-Chuong Duong Vrain, Christel Univ Orleans INSA Ctr Val Loire LIFO EA 4022 F-45067 Orleans France

Constrained Clustering allows to make the clustering task more accurate by integrating user constraints, which can be instance-level or cluster-level constraints. Few works consider the integration of different kinds of constraints, they are usually based on declarative frameworks and they are often exact methods, which either enumerate all the solutions satisfying the user constraints, or find a global optimum when an optimization criterion is specified. In a previous work, we have proposed a model for Constrained Clustering based on a constraint programming framework. It is declarative, allowing a user to integrate user constraints and to choose an optimization criterion among several ones. In this article we present a new and substantially improved model for Constrained Clustering, still based on a constraint programming framework. It differs from our earlier model in the way partitions are represented by means of variables and constraints. It is also more flexible since the number of clusters does not need to be set beforehand;only a lower and an upper bound on the number of clusters have to be provided. In order to make the model-based approach more efficient, we propose new global optimization constraints with dedicated filtering algorithms. We show that such a framework can easily be embedded in a more general process and we illustrate this on the problem of finding the optimal Pareto front of a bi-criterion constrained clustering task. We compare our approach with existing exact approaches, based either on a branch-and-bound approach or on graph coloring on twelve datasets. Experiments show that the model outperforms exact approaches in most cases. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Constrained clustering Bi-criterion clustering constraint programming Modeling Global optimization constraint Filtering algorithm

来源：评论

学校读者我要写书评

暂无评论

Using constraint programming for solving RCPSP/max-cal

引用

constraintS 2017年第3期22卷 432-462页

作者： Kreter, Stefan Schutt, Andreas Stuckey, Peter J. Tech Univ Clausthal Inst Management & Econ Operat Res Grp D-38678 Clausthal Zellerfeld Germany CSIRO Data61 Decis Sci Melbourne Vic Australia Univ Melbourne Dept Comp & Informat Syst Melbourne Vic 3010 Australia

Resource-constrained project scheduling with the objective of minimizing project duration (RCPSP) is one of the most studied scheduling problems. In this paper we consider the RCPSP with general temporal constraints and calendar constraints. Calendar constraints make some resources unavailable on certain days in the scheduling period and force activity execution to be delayed while resources are unavailable. They arise in practice from, e.g., unavailabilities of staff during public holidays and weekends. The resulting problems are challenging optimization problems. We develop not only six different constraint programming (CP) models to tackle the problem, but also a specialized propagator for the cumulative resource constraints taking the calendar constraints into account. This propagator includes the ability to explain its inferences so it can be used in a lazy clause generation solver. We compare these models, and different search strategies on a challenging set of benchmarks using the lazy clause generation solver chuffed and IBM CPLEX CP Optimizer, respectively. We close all but 8 of the open problems of the benchmark set, extend the benchmark set by instances with up to 500 activities, and show that CP solutions are highly competitive with existing Mip models of the problem.

关键词： RCPSP/max-cal constraint programming Lazy clause generation Calendars General temporal constraints

来源：评论

学校读者我要写书评

暂无评论

A new constraint programming approach for optimising a coal rail system

引用

OPTIMIZATION LETTERS 2017年第4期11卷 725-738页

作者： Masoud, Mahmoud Kozan, Erhan Kent, Geoff Liu, Shi Qiang Queensland Univ Technol Sci & Engn Fac GPO Box 2434 Brisbane Qld 4001 Australia

Because of the bottlenecking operations in a complex coal rail system, millions of dollars are costed by mining companies. To handle this issue, this paper investigates a real-world coal rail system and aims to optimise the coal railing operations under constraints of limited resources (e.g., limited number of locomotives and wagons). In the literature, most studies considered the train scheduling problem on a single-track railway network to be strongly NP-hard and thus developed metaheuristics as the main solution methods. In this paper, a new mathematical programming model is formulated and coded by optimization programming language based on a constraint programming (CP) approach. A new depth-first-search technique is developed and embedded inside the CP model to obtain the optimised coal railing timetable efficiently. Computational experiments demonstrate that high-quality solutions are obtainable in industry-scale applications. To provide insightful decisions, sensitivity analysis is conducted in terms of different scenarios and specific criteria.

关键词： Train scheduling Rail transportation Coal mining constraint programming

来源：评论

学校读者我要写书评

暂无评论

Scheduling double round-robin tournaments with divisional play using constraint programming

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第3期259卷 1180-1190页

作者： Carlsson, Mats Johansson, Mikael Larson, Jeffrey SICS POB 1263 SE-16429 Kista Sweden KTH Automat Control Lab Osquldas Vag 10 SE-10044 Stockholm Sweden Argonne Natl Lab MCS Div Lemont IL 60439 USA

We study a tournament format that extends a traditional double round-robin format with divisional single round-robin tournaments. Elitserien, the top Swedish handball league, uses such a format for its league schedule. We present a constraint programming model that characterizes the general double round-robin plus divisional single round-robin format. This integrated model allows scheduling to be performed in a single step, as opposed to common multistep approaches that decompose scheduling into smaller problems and possibly miss optimal solutions. In addition to general constraints, we introduce Elitserien-specific requirements for its tournament. These general and league-specific constraints allow us to identify implicit and symmetry-breaking properties that reduce the time to solution from hours to seconds. A scalability study of the number of teams shows that our approach is reasonably fast for even larger league sizes. The experimental evaluation of the integrated approach takes considerably less computational effort to schedule Elitserien than does the previous decomposed approach. (C) 2016 Elsevier B.V. All rights reserved.

关键词： OR in sports Scheduling constraint programming

来源：评论

学校读者我要写书评

暂无评论

A Hybrid Approach for the Sudoku Problem: Using constraint programming in Iterated Local Search

引用

IEEE INTELLIGENT SYSTEMS 2017年第2期32卷 52-62页

作者： Musliu, Nysret Winter, Felix Vienna Univ Technol Inst Informat Syst Vienna Austria

Sudoku is not only a popular puzzle but also an interesting and challenging constraint satisfaction problem. Therefore, automatic solving methods have been the subject of several publications in the past two decades. Although current methods provide good solutions for small-sized puzzles, larger instances remain challenging. This article introduces a new local search technique based on the min-conflicts heuristic for Sudoku. Furthermore, the authors propose an innovative hybrid search technique that exploits constraint programming as a perturbation technique within the iterated local search framework. They experimentally evaluate their methods on challenging benchmarks for Sudoku and report improvements over state-of-the-art solutions. To show the generalizability of the proposed approach, they also applied their method on another challenging scheduling problem. The results show that the proposed method is also robust in another problem domain.

关键词： Search problems programming Cost function Intelligent systems Stochastic processes Perturbation methods Heuristic algorithms INSPEC: Controlled Indexing constraint handling constraint satisfaction problems game theory mathematics computing perturbation techniques search problems INSPEC: Non-Controlled Indexing constraint programming iterated local search constraint satisfaction problem min-conflict heuristic perturbation technique logic puzzle scheduling problem automatic solving methods small-sized puzzles Sudoku hybrid search technique Author Keywords heuristic methods Sudoku iterated local search constraint programming min-conflicts heuristic hybrid techniques intelligent systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：