A new interval constraint propagation algorithm;called MOnotonic Hall Consistency (Mohc), has recently been proposed. Mohc exploits monotonicity of functions to better filter variable domains. Embedded in an interval-...
详细信息
ISBN:
(纸本)9783642153952
A new interval constraint propagation algorithm;called MOnotonic Hall Consistency (Mohc), has recently been proposed. Mohc exploits monotonicity of functions to better filter variable domains. Embedded in an interval-based solver, Mohc shows very high performance for solving systems of numerical constraints (equations or inequalities) over the reals. However, the main drawback is that its revise procedure depends on two user-defined parameters. this paper reports a rigourous empirical study resulting in a variant of Mohc that avoids a manual tuning of the parameters. In particular, we propose a policy to adjust in an auto-adaptive way;during the search, the parameter sensitive to the monotonicity of the revised function.
this paper presents a constraintprogramming model and search strategy to formulate and solve staff scheduling problems in health care. this is a well-studied problem for which many different approaches have been deve...
详细信息
ISBN:
(纸本)3540202021
this paper presents a constraintprogramming model and search strategy to formulate and solve staff scheduling problems in health care. this is a well-studied problem for which many different approaches have been developed over the years but it remains a challenge to successfully apply any given instance of a method to the various contexts encountered. We show how the main categories of rules involved may be expressed using global constraints. We describe a modular architecture for heuristic search. the resulting flexible and rather general constraintprogramming approach is evaluated on benchmark problems from different hospitals and for different types of personnel.
this paper presents the results of a case study, concerning the propagation of a global disjunctive resource constraint, when the resource is over-loaded. the problem can be seen as a partial constraint satisfaction p...
详细信息
ISBN:
(纸本)3540652248
this paper presents the results of a case study, concerning the propagation of a global disjunctive resource constraint, when the resource is over-loaded. the problem can be seen as a partial constraint satisfaction problem, in which either the resource constraint or the due dates of some jobs have to be violated. Global constraint propagation methods are introduced to efficiently deal withthis situation. these methods are applied to a well-known operations research problem: minimizing the number of late jobs on a single machine, when jobs are subjected to release dates and due dates. Dominance criteria and a branch and bound procedure are developed for this problem. 960 instances are generated with respect to different characteristics (number of jobs, overload ratio, distribution of release dales, of due dates and of processing times). Instances with 60 jobs are solved in 23 seconds on average and 90% of the instances with 100 jobs are solved in less than 1 hour.
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a ...
详细信息
ISBN:
(纸本)3540202021
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints;the problem is to decide whether or not the larger set of constraints has a satisfying assignment. this model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.
Local search algorithms have been very successful for solving constraint satisfaction problems (CSP). However, a major weakness has been that local search is unable to detect unsolvability and is thus not suitable for...
详细信息
ISBN:
(纸本)3540202021
Local search algorithms have been very successful for solving constraint satisfaction problems (CSP). However, a major weakness has been that local search is unable to detect unsolvability and is thus not suitable for highly constrained or overconstrained problems. In this paper, we present a scheme where a local search algorithm, the break-out algorithm, is used to identify hard or unsolvable subproblems and to derive a variable ordering that places the hardest subproblems first.
this paper considers the combination of berth and crane allocation problems in container terminals. We propose a novel approach based on constraintprogramming which is able to model many realistic operational constra...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
this paper considers the combination of berth and crane allocation problems in container terminals. We propose a novel approach based on constraintprogramming which is able to model many realistic operational constraints. the costs for berth allocation, crane allocation, time windows, breaks and transition times during gang movements are optimized simultaneously. the model is based on a resource view where gangs are consumed by vessel activities. Side constraints are added independently around this core model. the model is richer than the state of the art in the operations research community. Experiments show that the model produces solutions with a cost gap of 1/10 (7,8%) to 1/5 (18,8%) compared to an ideal operational setting where operational constraints are ignored.
In Online Problem Solving, partial solutions must be generated and executed before the complete problem is known. Many potential applications of constraintprogramming turn out to be online problems – for e...
ISBN:
(纸本)3540232419
In Online Problem Solving, partial solutions must be generated and executed before the complete problem is known. Many potential applications of constraintprogramming turn out to be online problems – for example, dynamic scheduling. How should we decide which values to assign to variables before all the variables and constraints are known? If we have some knowledge of the possible future developments of the problem, can we use that knowledge to make our initial assignments?
In this paper, we propose a general extension of constraint propagation for constraint optimization based on cooperative computation. It is similar both in principle and operations to constraint propagation. In princi...
详细信息
ISBN:
(纸本)3540232419
In this paper, we propose a general extension of constraint propagation for constraint optimization based on cooperative computation. It is similar both in principle and operations to constraint propagation. In principle, it eliminates variable values by checking the feasibility that they can be in any global optimum. In operations, it is based on parallel, local iterative computations. the proposed algorithm returns both a solution and a global lower bound at each iteration. As an approximation algorithm for optimization, it significantly outperform classical optimization methods, such as simulated annealing and local search with multi-restarts in practice.
We introduce a constraint for one-dimensional bin packing. this constraint uses propagation rules incorporating knapsack-based reasoning, as well as a lower bound on the number of bins needed. We show that this constr...
详细信息
ISBN:
(纸本)3540232419
We introduce a constraint for one-dimensional bin packing. this constraint uses propagation rules incorporating knapsack-based reasoning, as well as a lower bound on the number of bins needed. We show that this constraint can significantly reduce search on bin packing problems. We also demonstrate that when coupled with a standard bin packing search strategy, our constraint can be a competitive alternative to established operations research bin packing algorithms.
Since the early 90's that constraint Logic programming (CLP) has been used to solve Combinatorial Search Problems. Generally, CLP has a good performance with highly constrained problems, but it lacks a "globa...
详细信息
ISBN:
(纸本)3540202021
Since the early 90's that constraint Logic programming (CLP) has been used to solve Combinatorial Search Problems. Generally, CLP has a good performance with highly constrained problems, but it lacks a "global perspective" of the search space, making the search for the optimal solution more difficult when the problems becomes larger and less constrained. On the other hand, Local Search Methods explore the search space directly through an "intelligent" construction of solution neighbourhoods, turning these methods suitable for solving less constrained and large search spaces problems. the aim of this paper is to present a hybridisation framework that allows combining Local Search methods withconstraint Logic programming. the first results demonstrate that while maintaining the CLP strengths it is possible to overcome their weaknesses and improve its search efficiency.
暂无评论