We study here a natural situation when constraint programming can be entirely reduced to rule-based programming. To this end we explain first how one can compute on constraint satisfaction problems using rules represe...
详细信息
We study here a natural situation when constraint programming can be entirely reduced to rule-based programming. To this end we explain first how one can compute on constraint satisfaction problems using rules represented by simple first-order formulas. Then we consider constraint satisfaction problems that are based on predefined. explicitly given constraints. To solve them we first derive rules from these explicitly given constraints and limit the computation process to a repeated application of these rules, combined with labeling. We consider two types of rule here, The first type, that we call equality rules, leads to a new notion of local consistency, called rule consistency that turns out to be weaker than arc consistency for constraints of arbitrary arity (called hyper-arc consistency in Marriott & Stuckey (1998)). For Boolean constraints rule consistency coincides with the closure under the well-known propagation rules for Boolean constraints, The second type of rules, that we call membership rules, yields a rule-based characterization of arc consistency. To show feasibility of this rule-based approach to constraint programming. we show how both types of rules can be automatically generated. as CHR rules of Fruhwirth (1995). This yields an implementation of this approach to programming by means of constraint logic programming. We illustrate the usefulness of this approach to constraint programming by discussing various examples, including Boolean constraints, two typical examples of many valued logics, constraints dealing with Waltz's language for describing polyhedral scenes, and Allen's qualitative approach to temporal logic.
Domain experts typically have detailed knowledge of the concepts that are used in their domain;however they often lack the technical skills needed to translate that knowledge into model-driven engineering (MDE) idioms...
详细信息
Domain experts typically have detailed knowledge of the concepts that are used in their domain;however they often lack the technical skills needed to translate that knowledge into model-driven engineering (MDE) idioms and technologies. Flexible or bottom-up modelling has been introduced to assist with the involvement of domain experts by promoting the use of simple drawing tools. In traditional MDE the engineering process starts with the definition of a metamodel which is used for the instantiation of models. In bottom-up MDE example models are defined at the beginning, letting the domain experts and language engineers focus on expressing the concepts rather than spending time on technical details of the metamodelling infrastructure. The metamodel is then created manually or inferred automatically. The flexibility that bottom-up MDE offers comes with the cost of having nodes in the example models left untyped. As a result, concepts that might be important for the definition of the domain will be ignored while the example models cannot be adequately re-used in future iterations of the language definition process. In this paper, we propose a novel approach that assists in the inference of the types of untyped model elements using constraint programming. We evaluate the proposed approach in a number of example models to identify the performance of the prediction mechanism and the benefits it offers. The reduction in the effort needed to complete the missing types reaches up to 91.45% compared to the scenario where the language engineers had to identify and complete the types without guidance. (C) 2016 The Authors. Published by Elsevier Ltd.
This study presents a constraint programming (CP) model for the quay crane scheduling problem (QCSP), which occurs at container terminals, with realistic constraints such as safety margins, travel times and precedence...
详细信息
This study presents a constraint programming (CP) model for the quay crane scheduling problem (QCSP), which occurs at container terminals, with realistic constraints such as safety margins, travel times and precedence relations. Next, QCSP with time windows and integrated crane assignment and scheduling problem, are discussed. The performance of the CP model is compared with that of algorithms presented in QCSP literature. The results of the computational experiments indicate that the CP model is able to produce good results while reducing the computational time, and is a robust and flexible alternative for different types of crane scheduling problems. (C) 2013 Elsevier Ltd. All rights reserved.
This paper surveys recent applications and advances of the constraint programming-based column generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is ...
详细信息
This paper surveys recent applications and advances of the constraint programming-based column generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by constraint programming (CP). This framework has been introduced to solve crew assignment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using CP are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the CP-based column generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad hoc networks.
We outline the development and performance of heuristic approaches to obtain prioritized load planning solutions for the embarkation of cargo onto the deck of an amphibious ship. The heuristic techniques are underpinn...
详细信息
We outline the development and performance of heuristic approaches to obtain prioritized load planning solutions for the embarkation of cargo onto the deck of an amphibious ship. The heuristic techniques are underpinned by a constraint programming paradigm and have been implemented in a Java-based software package called COmPacT (constraint Optimization Packing Tool). COmPacT utilizes the modeling and solver libraries of the IBM ILOG CPLEX Optimization Studio. For the purposes of mathematical modeling, the embarkation planning problem is akin to packing a set of rectangular items onto a larger rectangular space (the deck), which could contain obstacles and may be subject to mass balance constraints. The modeling and algorithmic approaches are outlined in connection to the software development of COmPacT. Finally, we demonstrate how COmPacT may be used in conjunction with a planner's knowledge and expertise to enable iterative packing techniques, thereby combining the strengths of both automated and manual methods.
One of the most important policies adopted in inventory control is the replenishment cycle policy. Such a policy provides an effective means of damping planning instability and coping with demand uncertainty. In this ...
详细信息
One of the most important policies adopted in inventory control is the replenishment cycle policy. Such a policy provides an effective means of damping planning instability and coping with demand uncertainty. In this paper we develop a constraint programming approach able to compute optimal replenishment cycle policy parameters under non-stationary stochastic demand, ordering, holding and shortage costs. We show how in our model it is possible to exploit the convexity of the cost-function during the search to dynamically compute bounds and perform cost-based filtering. Our computational experience show the effectiveness of our approach. Furthermore, we use the optimal solutions to analyze the quality of the solutions provided by an existing approximate mixed integer programming approach that exploits a piecewise linear approximation for the cost function.
This paper surveys recent applications and advances of the constraint programming-based Column Generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is ...
详细信息
This paper surveys recent applications and advances of the constraint programming-based Column Generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by constraint programming. This framework has been introduced to solve crew assignment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using constraint programming are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the constraint programming-based Column Generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad-hoc networks.
Conway's game of Life provides an interesting testbed for exploring issues in formulation, symmetry, and optimization with constraint programming and hybrid constraint programming/ integer programming methods. We ...
详细信息
Conway's game of Life provides an interesting testbed for exploring issues in formulation, symmetry, and optimization with constraint programming and hybrid constraint programming/ integer programming methods. We consider three Life pattern- creation problems: finding maximum density still- Lifes, finding smallest immediate predecessor patterns, and finding period- 2 oscillators. For the first two problems, integrating integer programming and constraint programming approaches provides a much better solution procedure than either individually. For the final problem, the constraint programming formulation provides the better approach.
Diagnostic reasoning is often based on abduction. Abductive inference consists in generation of hypotheses which explain the current behavior of the system under investigation. Such a reasoning is based on accessible ...
详细信息
ISBN:
(纸本)9783319644745;9783319644738
Diagnostic reasoning is often based on abduction. Abductive inference consists in generation of hypotheses which explain the current behavior of the system under investigation. Such a reasoning is based on accessible background knowledge and the results must be consistent with all auxiliary observations. Efficient abductive diagnosis is carried out as Model-Based Reasoning. The knowledge about the model defines the search-space for diagnostic hypotheses. Unfortunately, use of classical consistency-based reasoning leads to rough, qualitative results only, even if good knowledge of the correct model is available. In this paper and attempt to use constraint programming as a tool for diagnostic reasoning is presented. The ultimate goal is to provide more precise diagnoses. Two case studies, one concerning fault parameter evaluation, and the second concerning structural fault localization are presented.
Genome Rearrangements addresses the problem of finding the minimum number of global operations, such as transpositions, reversals, fusions and fissions that transform a given genome into another. In this paper we deal...
详细信息
ISBN:
(纸本)9783642032226
Genome Rearrangements addresses the problem of finding the minimum number of global operations, such as transpositions, reversals, fusions and fissions that transform a given genome into another. In this paper we deal with transposition events, which are events that change the position of two contiguous block of genes in the same chromosome. The transposition event generates the transposition distance problem, that is to find the minimum number of transposition that transform one genome (or chromosome) into another. Although some tractables instances were found [20, 14], it is not known if an exact polynomial time algorithm exists. Recently, Dias and Souza [9] proposed polynomial-sized Integer Linear programming (ILP) models for rearrangement distance problems where events are restricted to reversals, transpositions or a combination of both. In this work we devise a slight different approach. We present some constraint Logic programming (CLP) models for transposition distance based on known bounds to the problem.
暂无评论