this paper introduces a generalization of the nvalue constraintthat bounds the number of distinct values taken by a set of variables. the generalized constraint (called nvector) bounds the number of distinct;vectors....
详细信息
ISBN:
(纸本)9783642042430
this paper introduces a generalization of the nvalue constraintthat bounds the number of distinct values taken by a set of variables. the generalized constraint (called nvector) bounds the number of distinct;vectors. the first contribution of this paper is to show that this global constraint has a significant role to play with continuous domains, by taking the example of simultaneous localization and map building (SLAM). this type of problem arises in the context, of mobile robotics. the second contribution is, to prove that enforcing bound consistency on this constraint is NP-complete. A simple contractor (or propagator) is proposed and applied on a real application.
We introduce a new method for solving systems of linear inequalities over the rationals-the conflict resolution method. the method successively refines an initial assignment withthe help of newly derived constraints ...
详细信息
ISBN:
(纸本)9783642042430
We introduce a new method for solving systems of linear inequalities over the rationals-the conflict resolution method. the method successively refines an initial assignment withthe help of newly derived constraints until either the assignment becomes a solution of the system or a trivially unsatisfiable constraint is derived. We show that this method is correct and terminating. Our experimental results show that conflict resolution outperforms the Fourier-Motzkin method and the Chernikov algorithm, in some cases by orders of magnitude.
In constraint Satisfaction, basic inferences rely oil some properties of constraint networks, called consistencies, that allow the identification of inconsistent instantiations (also called nogoods). Two main families...
详细信息
ISBN:
(纸本)9783642042430
In constraint Satisfaction, basic inferences rely oil some properties of constraint networks, called consistencies, that allow the identification of inconsistent instantiations (also called nogoods). Two main families of consistencies have been introduced so far: those that permit LIS to reason from variables Such as (i, j)-consistency and those that permit us to reason from constraints Such as relational (i, j)-consistency. this paper introduces a new family of consistencies based on the concept of flailed value (a value pruned during search). this family is orthogonal to previous ones.
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.
this paper considers the automatic generation of architectural tests (ATGP), a fundamental problem in processor validation. ATGPs are complex conditional constraint satisfaction problems which typically feature both h...
详细信息
ISBN:
(纸本)9783642042430
this paper considers the automatic generation of architectural tests (ATGP), a fundamental problem in processor validation. ATGPs are complex conditional constraint satisfaction problems which typically feature both hard and soft constraints and very large domains (e.g., all memory addresses). Moreover, the goal is to generate a. large number of diverse Solutions under tight runtime constraints. To improve solution diversity, this paper proposes a, novel approach to ATGPs by modeling them as MAXDIVERSEkSET problems and solving them withconstraint-based local search over conditional variables. the paper presents the semantics and implementation of Conditional variables in this context and demonstrates the computational benefits of the approach.
constraints have played a central role in cp because they capture key substructures of a problem and efficiently exploit them to boost inference. this paper intends to do the same thing for search, proposing constrain...
详细信息
constraints have played a central role in cp because they capture key substructures of a problem and efficiently exploit them to boost inference. this paper intends to do the same thing for search, proposing constraint-centered heuristics which guide the exploration of the search space toward areas that are likely to contain a high number of solutions. We first propose new search heuristics based on solution counting information at the level of individual constraints. We then describe efficient algorithms to evaluate the number of solutions of two important families of constraints: occurrence counting constraints, such as all different, and sequencing constraints, such as regular. In both cases we take advantage of existing filtering algorithms to speed up the evaluation. Experimental results on benchmark problems show the effectiveness of our approach.
In this paper, we show how model-checking can be generalized to temporal logic constraint solving, by considering temporal logic formulae with free variables over some domain D, and by computing a validity domain for ...
详细信息
ISBN:
(纸本)9783642042430
In this paper, we show how model-checking can be generalized to temporal logic constraint solving, by considering temporal logic formulae with free variables over some domain D, and by computing a validity domain for the variables rather than a truth value for the formula. this allows us to define a continuous degree of satisfaction for a temporal logic formula ill a, given structure, opening up the field of model-checking to optimization. We illustrate this approach with reverse engineering problems coming from systems biology, and provide some performance figures oil parameter optimization problems with respect to temporal logic specifications.
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.
Visualization is often invaluable to understand the behavior of optimization algorithms, identify their bottlenecks or pathological behaviors, and suggest remedial techniques. Yet developing visualizations is often a ...
详细信息
Visualization is often invaluable to understand the behavior of optimization algorithms, identify their bottlenecks or pathological behaviors, and suggest remedial techniques. Yet developing visualizations is often a tedious activity requiring significant time and expertise. this paper presents a framework for the visualization of constraint-based local search (CBLS) algorithms. Given a high-level model and a declarative visualization specification, the CBLS visualizer systematically produces animations to visualize constraints and objectives, violations, and conflicts, as well as the temporal behavior of these measures. the visualization specification is declarative and typically composed of a triple (what,where,how) indicating what to display, where, and with which graphical objects. the visualizer architecture is compositional and extensible. It provides building blocks which can be assembled freely by the user and focuses almost exclusively on static aspects, the dynamic aspects being automated by the use of invariants. the paper highlights various functionalities of the visualizer and describes a blueprint for its implementation.
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.
暂无评论