The paper proposes an original approach to solving the problem of ineffective processing of qualitative constraints of a subject domain using the constraint programming technique. The approach is based on the use of s...
详细信息
ISBN:
(纸本)9781614999331;9781614999324
The paper proposes an original approach to solving the problem of ineffective processing of qualitative constraints of a subject domain using the constraint programming technique. The approach is based on the use of specialized matrix-like structures providing a "compressed" representation of constraints over finite domains, as well as on the use of the authors' inference techniques on these structures. In comparison with the prototypes using the typical representation of multi-place relations in the form of a table, the techniques make it possible to more efficiently reduce the search space. The paper presents practical aspects of implementation of user-developed types of constraints and corresponding algorithmspropagators, with the help of constraint programming libraries. The algorithms performance has been assessed by means of the above matrix structures to clearly demonstrate the advantages of representation and processing of qualitative constraints of a subject domain.
OPL is a modeling language for mathematical programming and combinatorial optimization problems. It is the first modeling language to combine high-level algebraic and set notations from modeling languages with a rich ...
详细信息
ISBN:
(数字)9783540481645
ISBN:
(纸本)3540665404
OPL is a modeling language for mathematical programming and combinatorial optimization problems. It is the first modeling language to combine high-level algebraic and set notations from modeling languages with a rich constraint language and the ability to specify search procedures and strategies that is the essence of constraint programming. In addition, OPL models can be controlled and composed using OPLSCRIPT, a script language that simplifies the development of applications that solve sequences of models, several instances of the same model, or a combination of both as in column-generation applications. This paper illustrates some of the functionalities of OPL for constraint programming using frequency allocation, sport-scheduling, and job-shop scheduling applications. It also illustrates how OPL models can be composed using OPLSCRIPT on a simple configuration example.
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 probl...
详细信息
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.
In recent years, there has been a significant increase in health expenditures due to population growth. In this context, hospital administrators have started to look for ways to use existing resources effectively. Ope...
详细信息
In recent years, there has been a significant increase in health expenditures due to population growth. In this context, hospital administrators have started to look for ways to use existing resources effectively. Operating rooms are one of the most important units of a hospital. The efficient use of these units is seen as a decrease in cost items and an increase in revenues. At this point, it is aimed to use the operating rooms effectively in this study. The fact that it contains many uncertainties and many stakeholders in its structure complicates the solution process of the operating room scheduling problem. In this study, planning was made that considered the uncertainty in the operation times and the surgeons, nurses, and anesthesiologists in the surgical team. To solve the problem, the logical modeling power of the constraint programming method and the power of the goal programming method to stretch rigid constraints were utilized. In the first stage, the balanced assignment of the surgical team (surgeon-nurse-anesthesiologist) was carried out, while in the second stage, operations were assigned to the operating rooms. The proposed model was evaluated according to the operating rooms' utilization rates and the solution's effectiveness. The results showed that the proposed model successfully created an effective and efficient schedule.
In the context of aircraft assembly lines, increasing the production rate and decreasing the operating costs are two important, and sometimes contradictory, objectives. In small assembly lines, sharing production reso...
详细信息
This paper introduces a novel approach for extracting the maximum number of non-overlapping test forms from a large collection of overlapping test sections assembled from a given item bank. The approach involves solvi...
详细信息
This paper introduces a novel approach for extracting the maximum number of non-overlapping test forms from a large collection of overlapping test sections assembled from a given item bank. The approach involves solving maximum set packing problems (MSPs). A branch-and-bound MSP algorithm is developed along with techniques adapted from constraint programming to estimate lower and upper bounds on the optimal MSP solution. The algorithm is general and can be applied in other applications including combinatorial auctions. The results of computer simulations and experiments with an operational item bank are presented.
We present a library called ToOLS for the design of complex tree search algorithms in constraint programming (CP). We separate the description of a search algorithm into three parts: a refinement-based search scheme t...
详细信息
We present a library called ToOLS for the design of complex tree search algorithms in constraint programming (CP). We separate the description of a search algorithm into three parts: a refinement-based search scheme that defines a complete search tree, a set of conditions for visiting nodes that specifies a parameterized partial exploration, and a strategy for combining several partial explorations. This library allows the expression of most of the partial, i.e. nonsystematic backtracking, search methods, and also a specific class of hybrid local/global search methods called large neighborhood search, which are very naturally suited to CP. Variants of these methods are easy to implement with the ToOLS primitives. We demonstrate the expressiveness and efficiency of the library by solving a satellite mission management benchmark that is a mix between a traveling salesman problem with time windows and a Knapsack problem. Several partial and hybrid search methods are compared. Our results dramatically outperform CP approaches based on classical depth-first search methods. (c) 2005 Elsevier Ltd. All rights reserved.
Planning research is recently concerned with the resolution of more realistic problems as evidenced in the many works and new extensions to the Planning Domain Definition Language (PDDL) to better approximate real pro...
详细信息
Planning research is recently concerned with the resolution of more realistic problems as evidenced in the many works and new extensions to the Planning Domain Definition Language (PDDL) to better approximate real problems. Researchers' works to push planning algorithms and capture more complex domains share an essential ingredient, namely the incorporation of new types of constraints. Adding constraints seems to be the way of approximating real problems: these constraints represent the duration of tasks, temporal and resource constraints, deadlines, soft constraints, etc., i.e. features that have been traditionally associated to the area of scheduling. This desired expressiveness can be achieved by augmenting the planning reasoning capabilities, at the cost of slightly deviating the planning process from its traditional implicit purpose, that is finding the causal structure of the plan. However, the resolution of complex domains with a great variety of different constraints may involve as much planning effort as scheduling effort (and perhaps the latter being more prominent in many problems). For this reason, in this paper we present a general approach to model those problems under a constraint programming formulation which allows us to represent and handle a wide range of constraints. Our work is based on the original model of CPT, an optimal temporal planner, and it extends the CPT's formulation to deal with more expressive constraints. We will show that our general formulation can be used for planning and/or scheduling, from scheduling a given complete plan to generating the whole plan from scratch. However, our contribution is not a new planner but a constraint programming formulation for representing highly-constrained planning + scheduling problems.
In the car-sequencing problem, a number of cars have to be sequenced on an assembly line respecting several constraints. This problem was addressed by both Operations Research (OR) and constraint programming (CP) comm...
详细信息
In the car-sequencing problem, a number of cars have to be sequenced on an assembly line respecting several constraints. This problem was addressed by both Operations Research (OR) and constraint programming (CP) communities, either as a decision problem or as an optimization problem. In this paper, we consider the decision variant of the car sequencing problem and we propose a systematic way to classify heuristics for solving it. This classification is based on a set of four criteria, and we consider all relevant combinations for these criteria. Some combinations correspond to common heuristics used in the past, whereas many others are novel. Not surprisingly, our empirical evaluation confirms earlier findings that specific heuristics are very important for efficiently solving the car-sequencing problem (see for instance Smith, 1996), in fact, often as important or more than the propagation method. Moreover, through a criteria analysis, we are able to get several new insights into what makes a good heuristic for this problem. In particular, we show that the criterion used to select the most constrained option is critical, and the best choice is fairly reliably the "load" of an option. Similarly, branching on the type of vehicle is more efficient than branching on the use of an option. Overall, we can therefore indicate with a relatively high confidence which is the most robust strategy, or at least outline a small set of potentially best strategies. Last, following a remark in Regin and Puget (1997) stating that the notion of slack used in heuristics induces a pruning rule, we propose an algorithm for this method and experimentally evaluate it, showing that, although computationally cheap and easy to implement, this is in practice a very efficient way to solve car-sequencing benchmarks. (C) 2014 Elsevier Ltd. All rights reserved.
This paper intends to address the distributed flexible job shop scheduling problem (DFJSP) with minimizing maximum completion time (makespan). In order to solve this problem, we propose four mixed integer linear progr...
详细信息
This paper intends to address the distributed flexible job shop scheduling problem (DFJSP) with minimizing maximum completion time (makespan). In order to solve this problem, we propose four mixed integer linear programming (MILP) models as well as a constraint programming (CP) model, among which four MILP models are formulated based on four different modeling ideas. MILP models are effective in solving small-scaled problems to optimality. DFJSP is NP-hard, therefore, we propose an efficient constraint programming (CP) model based on interval decision variables and domain filtering algorithms. Numerical experiments are conducted to evaluate the performance of the proposed MILP models and CP model. The results show that the sequence-based MILP model is the most efficient one, and the proposed CP model is effective in finding good quality solutions for the both the small-sized and large-sized instances. The CP model incomparably outperforms the state-of-the-art algorithms and obtains new best solutions for 11 benchmark problems. Moreover, the best MILP model and CP model have proved the optimality of 62 best-known solutions.
暂无评论