constraint modelling is widely recognised as a key bottleneck in applying constraint solving to a problem of interest. the CONJURE automated constraint modelling system addresses this problem by automatically refining...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
constraint modelling is widely recognised as a key bottleneck in applying constraint solving to a problem of interest. the CONJURE automated constraint modelling system addresses this problem by automatically refining constraint models from problem specifications written in the ESSENCE language. ESSENCE provides familiar mathematical concepts like sets, functions and relations nested to any depth. To date, CONJURE has been able to produce a set of alternative model kernels (i.e. without advanced features such as symmetry breaking or implied constraints) for a given specification. the first contribution of this paper is a method by which CONJURE can break symmetry in a model as it is introduced by the modelling process. this works at the problem class level, rather than just individual instances, and does not require an expensive detection step after the model has been formulated. this allows CONJURE to produce a higher quality set of models. A further limitation of CONJURE has been the lack of a mechanism to select among the models it produces. the second contribution of this paper is to present two such mechanisms, allowing effective models to be chosen automatically.
In 2004, Jean-Francois Puget presented [2] an analysis of the "simplicity of Use" of constraintprogramming from which he articulated a series of challenges to make constraintprogramming systems accessible ...
详细信息
Filtering algorithms for table constraints are constraint-based, which means that the propagation queue only contains information on the constraints that must be reconsidered. this paper proposes four efficient value-...
详细信息
Today many companies face the challenge of matching highly-skilled professionals to high-end positions in large organizations and human deployment agencies. Non-accurate matches in these businesses can result in signi...
详细信息
ISBN:
(纸本)9783642153952
Today many companies face the challenge of matching highly-skilled professionals to high-end positions in large organizations and human deployment agencies. Non-accurate matches in these businesses can result in significant monetary losses and other negative effects. Unlike traditional Workforce Management (WM) problems such as shift scheduling, highly-skilled employees are professionally distinguishable from each other and hence non-interchangeable. therefore, the techniques used for shift-scheduling can't be applied to the highly-skilled WM domain. Our work focuses on providing a constraintprogramming solution for supporting the assignment of highly-skilled professionals. Our experience shows that cp is well adapted to this problem. cp supports very well the underlying constraints. In addition, the rich expressive language supported by cp allows us to provide a convenient mechanism for changing and adding new matching and preference constraints. Based on this technology, we have built a tool that is currently being used by IBM service organizations and provides strong business results.
Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their service. the configuration of a feature subscription involves choosing and sequenc...
详细信息
ISBN:
(纸本)9783540859574
Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their service. the configuration of a feature subscription involves choosing and sequencing features from a catalogue and is subject to constraints that prevent undesirable feature interactions at run-time. When the subscription requested by a user is inconsistent, one problem is to find an optimal relaxation. In this paper, we show that this problem is NP-hard and we present a constraintprogramming formulation using the variable weighted constraint satisfaction problem framework. We also present simple formulations using partial weighted maximum satisfiability and integer linear programming. We experimentally compare our formulations of the different approaches;the results suggest that our constraintprogramming approach is the best of the three overall.
Decomposition is it powerful technique for reducing the size of a backtracking search tree. However, when solving constraint optimization problems (COP'S) the standard technique of invoking a separate recursion to...
详细信息
ISBN:
(纸本)9783540859574
Decomposition is it powerful technique for reducing the size of a backtracking search tree. However, when solving constraint optimization problems (COP'S) the standard technique of invoking a separate recursion to solve each independent component can significantly reduce the strength of the bounds that can be applied when using branch rind bound techniques. In this paper we present a new search algorithm that can obtain many of the computational benefits of decomposition without having to resort to separate recursions. that is, the algorithm explores a standard OR tree not an AND-OR tree. In this way incremental information gathered from any component can be immediately applied to improve the bounding information for all of the other components. We also discuss how caching and local propagation can be combined with our approach and finally test our methods empirically to verify their potential.
the Cell BE processor provides both scalable computation power and flexibility, and it is already being adopted for many computational intensive applications like aerospace, defense, medical imaging and gaming. Despit...
详细信息
ISBN:
(纸本)9783540859574
the Cell BE processor provides both scalable computation power and flexibility, and it is already being adopted for many computational intensive applications like aerospace, defense, medical imaging and gaming. Despite of its merits, it also presents many challenges. as it is now widely known that is very difficult to program the Cell BE in an efficient manner. Hence, the creation of an efficient software development framework is becoming the key challenge for this computational platform. We have developed a novel software toolkit, called Cellflow, which enables developers to quickly build multi-task applications for Cell-based platform. We support programmers from the initial stage of their work, through a development-time software infrastructure, to the final stage of the application development, proposing a safe and easy-to-use explicit parallel programming model. A fundamental component of the software toolkit is the off-line allocator and scheduler that manages hardware resources while optimizing performance metrics such as execution time, allocation costs, power. the optimization engine receives as input a task graph representing an application, the hardware resources and produces an optimal allocation and scheduling. We have developed various approaches, either based on decomposition [5] or based on pure constraintprogramming, this latter being the core of this paper. We have identified instance features that guide toward the choice of the best solver for the instance at hand. Experimental result show that constraintprogramming (possibly combined with Integer programming) is a proper tool for dealing withthis kind of applications achieving very good performance.
this book constitutes the refereed proceedings of the 14thinternationalconference on principles and practice of constraintprogramming, cp 2008, Sydney, Australia, September, 2008. the 27 revised full papers and 23 ...
详细信息
ISBN:
(数字)9783540859581
ISBN:
(纸本)9783540859574
this book constitutes the refereed proceedings of the 14thinternationalconference on principles and practice of constraintprogramming, cp 2008, Sydney, Australia, September, 2008. the 27 revised full papers and 23 revised short papers presented together with 6 application papers and the abstracts of one invited lecture were carefully reviewed and selected from 120 submissions. All current issues of computing withconstraints are addressed, ranging from methodological and foundational aspects - using algorithms, environments, languages, models and systems - to solving real-world problems in various application fields.
Motivated by the performance improvements made to SAT solvers in recent years, a number of different encodings of constraints into SAT have been proposed. Concrete examples are the different SAT encodings for <= 1 ...
详细信息
ISBN:
(纸本)9783540749691
Motivated by the performance improvements made to SAT solvers in recent years, a number of different encodings of constraints into SAT have been proposed. Concrete examples are the different SAT encodings for <= 1 (x(1),..., x(n)) constraints. the most widely used encoding is known as the pairwise encoding, which is quadratic in the number of variables in the constraint. Alternative encodings are in general linear, and require using additional auxiliary variables. In most settings, the pairwise encoding performs acceptably well, but can require unacceptably large Boolean formulas. In contrast, linear encodings yield much smaller Boolean formulas, but in practice SAT solvers often perform unpredictably. this lack of predictability is mostly due to the large number of auxiliary variables that need to be added to the resulting Boolean formula. this paper studies one specific encoding for <= 1 (x(1),...,x(n)) constraints, and shows how a state-of-the-art SAT solver can be adapted to overcome the problem of adding additional auxiliary variables. Moreover, the paper shows that a SAT solver may essentially ignore the existence of auxiliary variables. Experimental results indicate that the modified SAT solver becomes significantly more robust on SAT encodings involving <= 1 (x(1),...,x(n)) constraints.
We present an incomplete filtering algorithm for the circuit constraint. the filter removes redundant values by eliminating nonhamiltonian edges from the associated graph. We identify nonhamiltonian edges by analyzing...
详细信息
ISBN:
(纸本)3540462678
We present an incomplete filtering algorithm for the circuit constraint. the filter removes redundant values by eliminating nonhamiltonian edges from the associated graph. We identify nonhamiltonian edges by analyzing a smaller graph with labeled edges that is defined on a separator of the original graph. the complexity of the procedure for each separator S is approximately O(vertical bar S vertical bar(5)). We found that it identified all infeasible instances and eliminated about one-third of the redundant domain elements in feasible instances.
暂无评论