In this paper we propose off-line and on-line extensions to the Resource Constrained Project Scheduling Problem. the off-line extension is a variant of RCPSP with time lags and uncertain, bounded activity durations. I...
详细信息
ISBN:
(纸本)9783642153952
In this paper we propose off-line and on-line extensions to the Resource Constrained Project Scheduling Problem. the off-line extension is a variant of RCPSP with time lags and uncertain, bounded activity durations. In this context we improve over our previous work presented in [12] by proposing an incremental flow computation for finding minimal conflict sets and a set of filtering rules for cumulative constraint propagation. the on-line extension is based instead on considering an on-line semantics such as the Self-Timed Execution and take it into account in the scheduling process. Adding the on-line aspect to the problem makes the CSP framework no longer suitable. We have extended the CSP framework to take into account general search decisions and auxiliary unbound variables. An extensive set of experimental results show an improvement
In this paper we present a hybrid model for the demand acceptance variant of the routing and wavelength assignment problem in directed networks, an important benchmark problem in optical network design. Our solution u...
详细信息
ISBN:
(纸本)9783642042430
In this paper we present a hybrid model for the demand acceptance variant of the routing and wavelength assignment problem in directed networks, an important benchmark problem in optical network design. Our solution uses a decomposition into a MIP model for the routing and optimization aspect, combined with a finite domain constraint model for the wavelength assignment. If a solution to the constraint problem is found, it provides an optimal Solution to the overall problem. If the constraint problem is infeasible, we use an extended explanation technique to find a good relaxation of the problem which leads to a near optimal solution. Extensive experiments show that proven optimality is achieved for more than 99.8% of all cases tested, while run-times are orders of magnitude smaller than the best known MIP solution.
Streamlined constraint reasoning is the addition of uninferred constraints to a constraint model to reduce the search space, while retaining at least one solution. Previously it has been established that it is possibl...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Streamlined constraint reasoning is the addition of uninferred constraints to a constraint model to reduce the search space, while retaining at least one solution. Previously it has been established that it is possible to generate streamliners automatically from abstract constraint specifications in Essence and that effective combinations of streamliners can allow instances of much larger scale to be solved. A shortcoming of the previous approach was the crude exploration of the power set of all combinations using depth and breadth first search. We present a new approach based on Monte Carlo search over the lattice of streamlined models, which efficiently identifies effective streamliner combinations.
We present an over-view of a system developed by IBM for generating short-term operations schedules for a large steel manufacturer. the problem addressed by the system was challenging due to the combination of detaile...
详细信息
ISBN:
(纸本)9783540749691
We present an over-view of a system developed by IBM for generating short-term operations schedules for a large steel manufacturer. the problem addressed by the system was challenging due to the combination of detailed resource allocation and scheduling constraints and preferences, sequence dependent setup times, tight minimum and maximum inventory level constraints between processes, and constraints on the minimum and maximum levels of production by shift for each product croup. We have developed a domain-specific decomposition based approach that uses mixed-integer programming to generate a high-level plan for production, and constraintprogramming to generate a schedule at fine level of time granularity taking into account detailed scheduling constraints and preferences. In this paper we give an overview of the problem domain and solution approach, and present a detailed description of the constraintprogramming part of the system. We also discuss the impact the system is having withthe customer on their manufacturing operations.
We establish optimal bounds on the number of nested propagation steps in k-consistency tests. It is known that local consistency algorithms such as arc-, path- and k-consistency are not efficiently parallelizable. the...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
We establish optimal bounds on the number of nested propagation steps in k-consistency tests. It is known that local consistency algorithms such as arc-, path- and k-consistency are not efficiently parallelizable. their inherent sequential nature is caused by long chains of nested propagation steps, which cannot be executed in parallel. this motivates the question "What is the minimum number of nested propagation steps that have to be performed by k-consistency algorithms on (binary) constraint networks with n variables and domain size d?" It was known before that 2-consistency requires Omega(nd) and 3-consistency requires Omega(n(2)) sequential propagation steps. We answer the question exhaustively for every k >= 2: there are binary constraint networks where any k-consistency procedure has to perform Omega( n(k-1)d(k-1)) nested propagation steps before local inconsistencies were detected. this bound is tight, because the overall number of propagation steps performed by k-consistency is at most n(k-1)d(k-1).
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.
VLSI chips design is becoming increasingly complex and calling for more and more automation. Many chip design problems can be formulated is constraint problems and are potentially amenable to CP techniques. To the bes...
详细信息
ISBN:
(纸本)9783642042430
VLSI chips design is becoming increasingly complex and calling for more and more automation. Many chip design problems can be formulated is constraint problems and are potentially amenable to CP techniques. To the best of our knowledge, though there has been little CP work in this domain to date. We describe a successful application of a CP based tool to a particular pin-assignment problem hi which tens of thousands of phis (i.e.;connection points) belonging to internal units on the chip must be placed within their units so as to satisfy certain constraints and optimize the wirability of the design. Our tool has been tested on read IBM designs and is now being integrated into IBM's chip development environment.
In this paper we consider the consistency problem for qualitative constraint networks representing temporal or spatial information. the most efficient method for solving this problem consists in a search algorithm usi...
详细信息
ISBN:
(纸本)9783540749691
In this paper we consider the consistency problem for qualitative constraint networks representing temporal or spatial information. the most efficient method for solving this problem consists in a search algorithm using, on the one hand, the weak composition closure method as a local propagation method, and on the other hand, a decomposition of the constraints into subrelations of a tractable set. We extend this algorithm withthe notion of eligibility and the notion of frozen constraints. the first concept allows to characterise constraints which will not be considered during the search. the second one allows to freeze constraints in order to avoid unnecessary updates.
Objective-CP is an optimization system that views an optimization program as the combination of a model, a search, and a solver. Models in Objective-CP follow the modeling style of constraintprogramming and are concr...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Objective-CP is an optimization system that views an optimization program as the combination of a model, a search, and a solver. Models in Objective-CP follow the modeling style of constraintprogramming and are concretized into specific solvers. Search procedures are specified in terms of high-level nondeterministic constructs, search combinators, and node selection strategies. Objective-CP supports fully transparent parallelization of multi-start and branch & bound algorithms. the implementation of Objective-CP is based on a sequence of model transformations, followed by a concretization step. Moreover, Objective-CP features a constraint-programming solver following a micro-kernel architecture for ease of maintenance and extensibility. Experimental results show the practicability of the approach.
this paper introduces CHRrp: constraint Handling Rules with user-definable rule priorities. CHRrp offers flexible execution control which is lacking in CHR. A formal operational semantics for the extended language is ...
详细信息
暂无评论