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 ...
详细信息
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.
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,...
详细信息
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
In simple assembly line balancing problems, it is assumed that the resources required to perform the tasks are available at the relevant station for task assignment. However, each task may need different resource type...
详细信息
In simple assembly line balancing problems, it is assumed that the resources required to perform the tasks are available at the relevant station for task assignment. However, each task may need different resource types depending on the difficulty, complexity and technical requirements of the tasks in real life. For this reason, tasks and resources belonging to these tasks must be assigned to the relevant station while balancing the line. In this study, the resource-constrained U-shaped assembly line balancing problem (U-GRCALBP) is discussed. According to the literature research, there is no study dealing with U-GRCALBP. Two different constraint programming (CP) models that define the resource constraints as "and/or" constraint types with concurrent resource types have been developed. In these models, the sum of resource usage costs and station opening cost minimization is aimed. The models are explained with an illustrative example and the efficiency of the models is tested by deriving new resource constraints on five different data set each taking into account four different cycle times and the number of two and four resource types. The number of stations obtained, the total number of resources used, total station opening and resource usage costs, and CPU time are used as performance criteria The results are compared with the traditional U-type assembly line balancing problem results. The proposed CP models give superior performance on all data sets, especially in terms of total cost. The numerical results show that both CP models are effective in solving the problem. Furthermore, some managerial implications are presented to be useful for professionals, organizations, and society.
solve machine learning problems, we have developed a method to identify closed sets of common features of objects (patterns) of the training sample. The novelty of the method lies in the fact that it is implemented wi...
详细信息
solve machine learning problems, we have developed a method to identify closed sets of common features of objects (patterns) of the training sample. The novelty of the method lies in the fact that it is implemented within the concept of constraint programming and uses a new type of table constraints-compressed tables of the D-type-for internal representation and processing of the training sample. Search reduction is achieved by applying the proposed method of branching the search tree and using partial order relations on sets of objects (features) to prune unpromising branches. The method has a computational complexity estimate that for some types of input data is better than the estimates obtained for the studied prototypes.
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) lan...
详细信息
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.
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 fo...
详细信息
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.
This paper presents a framework taking advantage of the capabilities of current constraint solvers to plan the work on construction sites. It combines different constraints under a common framework to facilitate the d...
详细信息
This paper presents a framework taking advantage of the capabilities of current constraint solvers to plan the work on construction sites. It combines different constraints under a common framework to facilitate the definition of temporal relations between different tasks and provides a user-friendly web interface, which facilitates the planning of construction sites. Even though the framework uses complex mathematical models, the users do not need to know the underlying theoretical framework. Another important feature of the framework is, in contrast to usual static planning, that solutions can be dynamically adapted to take into account delays happening during the actual construction process. In order to show the applicability of the methodology, the paperspaper shows how a real construction project can be planned by using the framework.
NoC technology is composed of packet-based interconnections, where the communication resources are distributed across the network. Therefore, the optimal resource utilization is a crucial consideration for efficient a...
详细信息
NoC technology is composed of packet-based interconnections, where the communication resources are distributed across the network. Therefore, the optimal resource utilization is a crucial consideration for efficient architectural designs. This paper studies the practicality of the constraint programming (CP) models for NoC architecture designs that effectively use a regular mesh with wormhole switching and the XY routing. The complexity of the CP models is compared with the earlier Mixed Integer programming (MIP) models. Practical CP-based mapping and scheduling models are developed and results are reported on the benchmark datasets. Results indicate that mapping and scheduling problems can be solved at near optimality even under relatively shorter run-time limits as compared to those required by the MIP models.
Qualitative modelling is a technique integrating the fields of theoretical computer science, artificial intelligence and the physical and biological sciences. The aim is to be able to model the behaviour of systems wi...
详细信息
Qualitative modelling is a technique integrating the fields of theoretical computer science, artificial intelligence and the physical and biological sciences. The aim is to be able to model the behaviour of systems without estimating parameter values and fixing the exact quantitative dynamics. Traditional applications are the study of the dynamics of physical and biological systems at a higher level of abstraction than that obtained by estimation of numerical parameter values for a fixed quantitative model. Qualitative modelling has been studied and implemented to varying degrees of sophistication in Petri nets, process calculi and constraint programming. In this paper we reflect on the strengths and weaknesses of existing frameworks, we demonstrate how recent advances in constraint programming can be leveraged to produce high quality qualitative models, and we describe the advances in theory and technology that would be needed to make constraint programming the best option for scientific investigation in the broadest sense.
This contribution presents an integrated constraint programming (CP) model to tackle the problems of tool allocation, machine loading, part routing. and scheduling in a flexible manufacturing system (FMS) The formulat...
详细信息
This contribution presents an integrated constraint programming (CP) model to tackle the problems of tool allocation, machine loading, part routing. and scheduling in a flexible manufacturing system (FMS) The formulation, Which is able to take into account a variety of constraints found in industrial environments, as well as several objective functions. has been Successfully applied to the Solution of various case studies of different sizes. Though some of the problem instances have bigger sizes than the examples reported to date in literature, very good-quality Solutions were reached in quite reasonable CPU times. This good computational performance is due to two essential characteristics of the proposed model. The most significant one IS the use of two sets of two-index variables to capture manufacturing activities instead of having Just one set of four indexes. Thus, dimensionality is greatly reduced. The other relevant feature is the fact that the model relies oil an Indirect representation of tool needs by means of tool types. thus avoiding the consideration of tool copies. (C) 2009 Elsevier Ltd. All rights reserved
暂无评论