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

A constraint programming approach to cutset problems

COMPUTERS & OPERATIONS RESEARCH 2006年第10期33卷 2852-2865页

作者： Fages, F Lal, A INRIA Rocquencourt Projet Contraintes F-78153 Le Chesnay France

We consider the problem of finding a cutset in a directed graph G = (V, E), i.e., a set of vertices that cuts all cycles in G. Finding a cutset of minimum cardinality is NP-hard. There exist several approximate and exact algorithms, most of them using graph reduction techniques. In this paper, we propose a constraint programming approach to cutset problems and design a global constraint for computing cutsets. This cutset constraint is a global constraint over boolean variables associated to the vertices of a given graph and states that the subgraph restricted to the vertices having their boolean variable set to true is acyclic. We propose a filtering algorithm based on graph contraction operations and inference of simple boolean constraints, that has a linear time complexity in O (vertical bar E vertical bar +/- vertical bar V vertical bar). We discuss search heuristics based on graph properties provided by the cutset constraint, and show the efficiency of the cutset constraint on benchmarks of the literature for pure minimum cutset problems, and on an application to log-based reconciliation problems where the global cutset constraint is mixed with other boolean constraints. (c) 2005 Published by Elsevier Ltd.

关键词： constraint programming global constraints cutset feedback vertex set reconciliation

来源：评论

学校读者我要写书评

暂无评论

A hybrid constraint programming approach to a wood procurement problem with bucking decisions

引用

constraintS 2016年第2期21卷 303-317页

作者： Dems, Amira Rousseau, Louis-Martin Frayret, Jean-Marc Ecole Polytech Montreal PQ H3C 3A7 Canada

In this article, we present a wood procurement problem that arises in Eastern Canada. We solve a multi-period wood supply planning problem, while taking into account bucking decisions. Furthermore, we present a new form of flexibility which allows the harvesting capacity to change from one time period to another. We study the impact of such flexibility upon the harvesting cost. We assess the performance of the problem by comparing it with a variant where the harvesting capacity is fixed during sites' harvesting. To address this problem, we develop a hybrid approach based on both constraint and mathematical programming. In the first phase, we propose a constraint programming model dealing with forest sites harvesting and bucking problems. The result of this model is used as part of an initial solution for the whole problem formulated as a mixed integer model. We test the two versions of the problem on a set of different demand instances and we compare their results.

关键词： Forest bucking problem Wood-procurement planning constraint programming Hybrid method

来源：评论

学校读者我要写书评

暂无评论

On the optimal modeling and evaluation of job shops with a total weighted tardiness objective: constraint programming vs. mixed integer programming

引用

APPLIED MATHEMATICAL MODELLING 2015年第2期39卷 955-964页

作者： Sahraeian, Rashed Namakshenas, Mohammad Shahed Univ Coll Engn Dept Ind Engn Tehran Iran

In this study we consider the mapping of the main characteristics, i.e., the structural properties, of a classical job shop problem onto well-known combinatorial techniques, i.e., positional sets, disjunctive graphs, and linear orderings. We procedurally formulate three different models in terms of mixed integer programming (MIP) and constraint programming (CP) paradigms. We utilize the properties of positional sets and disjunctive graphs to construct tight MIP formulations in an efficient manner. In addition, the properties are retrieved by the polyhedral structures of the linear ordering and they are defined on a disjunctive graph to facilitate the formulation of the CP model and to reduce the number of dominant variables. The proposed models are solved and their computational performance levels are compared with well-known benchmarks in the job shop research area using IBM ILog Cplex software. We provide a more explicit analogy of the applicability of the proposed models based on parameters such as time efficiency, thereby producing strong bounds, as well as the expressive power of the modeling process. We also discuss the results to determine the best formulation, which is computationally efficient and structurally parsimonious with respect to different criteria. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Combinatorics constraint programming Job shop Mixed integer programming Total weighted tardiness

来源：评论

学校读者我要写书评

暂无评论

A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences

引用

constraintS 2022年第3期27卷 249-283页

作者： Cseh, Agnes Escamocher, Guillaume Genc, Begum Quesada, Luis Ctr Econ & Reg Studies Inst Econ Budapest Hungary Univ Coll Dublin Insight Ctr Data Analyt Dublin 4 Cork Dublin Ireland Univ Coll Cork Sch Comp Sci & Informat Technol Cork Ireland Confirm Ctr Smart Mfg Cork V94 C928 Ireland

We introduce five constraint models for the 3-dimensional stable matching problem with cyclic preferences and study their relative performances under diverse configurations. While several constraint models have been proposed for variants of the two-dimensional stable matching problem, we are the first to present constraint models for a higher number of dimensions. We show for all five models how to capture two different stability notions, namely weak and strong stability. Additionally, we translate some well-known fairness notions (i.e. sex-equal, minimum regret, egalitarian) into 3-dimensional matchings, and present how to capture them in each model. Our tests cover dozens of problem sizes and four different instance generation methods. We explore two levels of commitment in our models: one where we have an individual variable for each agent (individual commitment), and another one where the determination of a variable involves pairing the three agents at once (group commitment). Our experiments show that the suitability of the commitment depends on the type of stability we are dealing with, and that the choice of the search heuristic can help improve performance. Our experiments not only brought light to the role that learning and restarts can play in solving this kind of problems, but also allowed us to discover that in some cases combining strong and weak stability leads to reduced runtimes for the latter.

关键词： Three-dimensional stable matching with cyclic preferences 3DSM-cyc constraint programming Fairness

来源：评论

学校读者我要写书评

暂无评论

Constrained multi-objective wind farm layout optimization: Novel constraint handling approach based on constraint programming

引用

RENEWABLE ENERGY 2018年 126卷 341-353页

作者： Sorkhabi, Sami Yamani Douzi Romero, David A. Beck, J. Christopher Amon, Cristina H. MIT Dept Mech Engn Cambridge MA 02139 USA Univ Toronto Dept Mech & Ind Engn Toronto ON Canada

Wind farms are frequently located in proximity to human dwellings, natural habitats, and infrastructure making land use constraints and noise matters of increasing concern for all stakeholders. In this study, we perform a constrained multi-objective wind farm layout optimization considering energy and noise as objective functions, and considering land use constraints arising from landowner participation, environmental setbacks and proximity to existing infrastructure. A multi-objective, continuous variable Genetic Algorithm (NSGA-II) is combined with a novel constraint handling approach to solve the optimization problem. This constraint handling approach uses a combination of penalty functions and constraint programming to balance local and global exploration to find feasible solutions. The proposed approach is used to solve the wind farm layout optimization problem with different numbers of turbines and under different levels of land availability (constraint severity). Our results show increasing land availability and/or number of turbines, increases energy generation, noise production, and computational cost. Results also illustrate the potential of the proposed constraint handling approach to outperform existing methods in the context of evolutionary optimization, yielding better solutions at a lower computational cost. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Wind farm layout Multi-objective optimization constraint programming Penalty functions

来源：评论

学校读者我要写书评

暂无评论

Mining diverse sets of patterns with constraint programming using the pairwise Jaccard similarity relaxation

引用

constraintS 2024年第1-2期29卷 80-111页

作者： Hien, Arnold Aribi, Noureddine Loudni, Samir Lebbah, Yahia Ouali, Abdelkader Zimmermann, Albrecht Univ Oran 1 Lab LITIO Oran 31000 Algeria IMT Atlantique TASC LS2N CNRS F-44307 Nantes France Normandie Univ CNRS UMR GREYC F-14000 Caen France

In recent years, pattern mining has evolved from a slow-moving, repetitive three-step process to a much more agile and iterative/user-centric mining model. A crucial element of this framework is the capability to rapidly provide a set of diverse patterns to the user. This paper proposes a pattern mining approach based on constraint programming that incorporates a non-redundancy/diversity constraint into closed pattern enumeration. The level of diversity is controlled through a threshold on the maximum pairwise Jaccard similarity of pattern occurrences. We show that the Jaccard measure does not have nice (anti-)monotonicity properties w.r.t. the general-to-specific enumeration. To address this limitation, we propose anti-monotonic lower and upper-bound relaxations of the Jaccard similarity with nice pruning-enabling properties, and connect the final results to the original Jaccard Index. To evaluate the effectiveness of our relaxations, we conduct a comprehensive comparison against several existing pattern mining techniques designed to control redundancy. Experimental results illustrate that our approach provides an effective solution for mining diverse itemsets, showing competitive performance in both runtime and flexibility.

关键词： constraint programming Pairwise Jaccard index Diversity Pattern mining Relaxation

来源：评论

学校读者我要写书评

暂无评论

Solving the integrated process planning and scheduling problem using an enhanced constraint programming-based approach

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2022年第18期60卷 5505-5522页

作者： Shi, Ganquan Yang, Zhouwang Xu, Yang Quan, Yuchen Univ Sci & Technol China Sch Math Sci Hefei Peoples R China Univ Sci & Technol China Sch Data Sci Hefei Peoples R China

Due to various factors of flexibility introduced into manufacturing systems, researchers have gradually shifted their focus to the integrated process planning and scheduling (IPPS) problem to improve productivity. The previous literature rarely associates IPPS with constraint programming, even though constraint programming has achieved success in the scheduling field. Furthermore, existing approaches are usually customized to certain types of IPPS problems and cannot handle the general problem. In this paper, with a view to obtaining the optimal AND/OR graph automatically, a depth first search generating algorithm is designed to convert the type-1 IPPS problem into our approach's standard input format. Moreover, we propose an approach based on enhanced constraint programming to cope with the general problem, employing advanced schemes to enhance the constraint propagation and improve the search efficiency. Our approach is implemented on ORTOOLS, and its superiority is verified by testing on 15 benchmarks with 50 instances. Experimental results indicate that 41 instances are solved optimally, among which the optimality of the solutions for 20 instances is newly confirmed, and the solutions of six instances are improved. Our approach is the first method to reach the overall optimum in the most influential benchmark with 24 instances.

关键词： integrated process planning and scheduling constraint programming AND OR graph graph-based model depth first search

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Solving the nuclear dismantling project scheduling problem by combining mixed-integer and constraint programming techniques and metaheuristics

引用

JOURNAL OF SCHEDULING 2021年第3期24卷 269-290页

作者： Hubner, Felix Gerhards, Patrick Stuerck, Christian Volk, Rebekka Karlsruhe Inst Technol KIT Inst Ind Prod IIP Karlsruhe Germany Helmut Schmidt Univ Inst Comp Sci Hamburg Germany Helmut Schmidt Univ Inst Management Sci & Operat Res Hamburg Germany

Scheduling of megaprojects is very challenging because of typical characteristics, such as expected long project durations, many activities with multiple modes, scarce resources, and investment decisions. Furthermore, each megaproject has additional specific characteristics to be considered. Since the number of nuclear dismantling projects is expected to increase considerably worldwide in the coming decades, we use this type of megaproject as an application case in this paper. Therefore, we consider the specific characteristics of constrained renewable and non-renewable resources, multiple modes, precedence relations with and without no-wait condition, and a cost minimisation objective. To reliably plan at minimum costs considering all relevant characteristics, scheduling methods can be applied. But the extensive literature review conducted did not reveal a scheduling method considering the special characteristics of nuclear dismantling projects. Consequently, we introduce a novel scheduling problem referred to as the nuclear dismantling project scheduling problem. Furthermore, we developed and implemented an effective metaheuristic to obtain feasible schedules for projects with about 300 activities. We tested our approach with real-life data of three different nuclear dismantling projects in Germany. On average, it took less than a second to find an initial feasible solution for our samples. This solution could be further improved using metaheuristic procedures and exact optimisation techniques such as mixed-integer programming and constraint programming. The computational study shows that utilising exact optimisation techniques is beneficial compared to standard metaheuristics. The main result is the development of an initial solution finding procedure and an adaptive large neighbourhood search with iterative destroy and recreate operations that is competitive with state-of-the-art methods of related problems. The described problem and findings can be transferred

关键词： Project scheduling Multi-mode resource investment problem Mixed-integer programming constraint programming Metaheuristic Nuclear dismantling project scheduling problem

来源：评论

学校读者我要写书评

暂无评论

Newton - constraint programming over nonlinear constraints

引用

SCIENCE OF COMPUTER programming 1998年第1-2期30卷 83-118页

作者： Van Hentenryck, P Michel, L Benhamou, F Brown Univ Providence RI 02912 USA Univ Orleans F-45067 Orleans France

This paper is an introduction to Newton, a constrain-programming language over nonlinear real constraints. Newton originates from an effort to reconcile the declarative nature of constraint logic programming (CLP) languages over intervals with advanced interval techniques developed in numerical analysis, such as the interval Newton method. Its key conceptual idea is to introduce the notion of box-consistency, which approximates are-consistency, a notion well-known in artificial intelligence. Box-consistency achieves an effective pruning at a reasonable computation cost and generalizes some traditional interval operators. Newton has been applied to numerous applications in science and engineering, including nonlinear equation-solving, unconstrained optimization, and constrained optimization. It is competitive with continuation methods on their equation-solving benchmarks and outperforms the interval-based methods we are aware of on optimization problems. (C) 1998 Elsevier Science B.V.

关键词： constraint programming nonlinear programming interval reasoning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：