this paper presents the first;experimental evaluation of the length-lex domain for set variables. the implementation is based on bound-consistency algorithms proposed in earlier work and two novel technical contributi...
详细信息
ISBN:
(纸本)9783642042430
this paper presents the first;experimental evaluation of the length-lex domain for set variables. the implementation is based on bound-consistency algorithms proposed in earlier work and two novel technical contributions: a generic filtering algorithm which automatically pushes ordering constraints into symmetric binary constraints with only a logarithmic overhead and an adaptation of symmetry-breaking constraints from 0/1 matrices to the length-lex ordering. the experimental results indicate that the length-lex representation for set variables is very effective and robust on traditional set-CSPs benchmarks.
We present a parallel solver for numerical constraint satisfaction problems (NCSPs) that can scale on a number of cores. Our proposed method runs worker solvers on the available cores and simultaneously the workers co...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
We present a parallel solver for numerical constraint satisfaction problems (NCSPs) that can scale on a number of cores. Our proposed method runs worker solvers on the available cores and simultaneously the workers cooperate for the search space distribution and balancing. In the experiments, we attained up to 119-fold speedup using 256 cores of a parallel computer.
this paper offers a critique of the framework of constraint Satisfaction Problems. While this framework has been successful in studying search techniques, and has inspired some constraintprogramming languages, it has...
详细信息
Multi-objective optimization is concerned with problems involving multiple Measures of performance which should be optimized simultaneously. In this paper, we extend AND/OR Branch-and-Bound (AOBB). a well known search...
详细信息
ISBN:
(纸本)9783642042430
Multi-objective optimization is concerned with problems involving multiple Measures of performance which should be optimized simultaneously. In this paper, we extend AND/OR Branch-and-Bound (AOBB). a well known search algorithm, from mono-objective to multi-objective optimization. the new algorithm MO-AOBB exploits efficiently the problem structure by traversing an AND/OR search tree and uses static and dynamic mini-bucket heuristics to guide the search. We show that MO-AOBB improves dramatically over the traditional OR search approach, on various benchmarks for multi-objective optimization.
Conditionals are a core concept in all programming languages. they are also a natural and powerful mechanism for expressing complex constraints in constraint modelling languages. the behaviour of conditionals is compl...
详细信息
ISBN:
(纸本)9783030300487
Conditionals are a core concept in all programming languages. they are also a natural and powerful mechanism for expressing complex constraints in constraint modelling languages. the behaviour of conditionals is complicated by undefinedness. In this paper we show how to most effectively translate conditional constraints for underlying solvers. We show that the simple translation into implications can be improved, at least in terms of reasoning strength, for bothconstraintprogramming and mixed integer programming solvers. Unit testing shows that the new translations are more efficient, but the benefits are not so clear on full models where the interaction with other features such as learning is more complicated.
We extend the common depth-first backtrack search for constraint satisfaction problems with randomized variable and value selection. the resulting methods are applied to real-world instances of the tail assignment pro...
详细信息
ISBN:
(纸本)3540462678
We extend the common depth-first backtrack search for constraint satisfaction problems with randomized variable and value selection. the resulting methods are applied to real-world instances of the tail assignment problem, a certain kind of airline planning problem. We analyze the performance impact of these extensions and, in order to exploit the improvements, add restarts to the search procedure. Finally computational results of the complete approach are discussed.
Stream constraintprogramming is a recent addition to the family of constraintprogramming frameworks, where variable domains are sets of infinite streams over finite alphabets. Previous works showed promising results...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Stream constraintprogramming is a recent addition to the family of constraintprogramming frameworks, where variable domains are sets of infinite streams over finite alphabets. Previous works showed promising results for its applicability to real-world planning and control problems. In this paper, motivated by the modelling of planning applications, we improve the expressiveness of the framework by introducing (1) the "until" constraint, a new construct that is adapted from Linear Temporal Logic and (2) the @ operator on streams, a syntactic sugar for which we provide a more efficient solving algorithm over simple desugaring. For both constructs, we propose corresponding novel solving algorithms and prove their correctness. We present competitive experimental results on the Missionaries and Cannibals logic puzzle and a standard path planning application on the grid, by comparing with Apt and Brand's method for verifying eventuality conditions using a CP approach.
this paper proposes the framework of branch-and-check with explanations (BCE), a branch-and-check method where combinatorial cuts are found by general-purpose conflict analysis, rather than by specialized separation a...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
this paper proposes the framework of branch-and-check with explanations (BCE), a branch-and-check method where combinatorial cuts are found by general-purpose conflict analysis, rather than by specialized separation algorithms. Specifically, the method features a master problem that ignores combinatorial constraints, and a feasibility sub-problem that uses propagation to check the feasibility of these constraints and performs conflict analysis to derive nogood cuts. the BCE method also leverages conflict-based branching rules and strengthens cuts in a post-processing step. Experimental results on the Vehicle Routing Problem with Time Windows show that BCE is a potential alternative to branch-and-cut. In particular, BCE dominates branch-and-cut, both in proving optimality and in finding high-quality solutions quickly.
this paper introduces an architecture for generic constraint implementations based on variable views and range iterators. Views allow, for example, to scale, translate, and negate variables. the paper shows how to mak...
详细信息
ISBN:
(纸本)3540292381
this paper introduces an architecture for generic constraint implementations based on variable views and range iterators. Views allow, for example, to scale, translate, and negate variables. the paper shows how to make constraint implementations generic and how to reuse a single generic implementation with different views for different constraints. Applications of views exemplify their usefulness and their potential for simplifying constraint implementations. We introduce domain operations compatible with views based on range iterators to access and modify entire variable domains.
the high-level and portable nature of the Java platform allows applications to be written once and executed on all the supported systems. However, such a feature comes at the cost of hardware abstraction, making it mo...
详细信息
暂无评论