the proceedings contain 62 papers. the topics discussed include: constraint-based schedulers, do they really work?;challenges for constraint reasoning and optimization in computational sustainability;observations on s...
ISBN:
(纸本)3642042430
the proceedings contain 62 papers. the topics discussed include: constraint-based schedulers, do they really work?;challenges for constraint reasoning and optimization in computational sustainability;observations on symmetry breaking;generating optimal stowage plans for container vessel bays;real-time Tabu search for video tracking association;pin assignment using stochastic local search constraintprogramming;modelling equidistant frequency permutation arrays: an application of constraints to mathematics;scheduling the CB1000 nanoproteomic analysis system with Python, Tailor, and Minion;solving nurse rostering problems using soft global constraints;online selection of quorum systems for RAMBO reconfiguration;a hybrid constraint model for the routing and wavelength assignment problem;memorisation for constraint-based local search;on the structure of industrial SAT instances;a gender-based genetic algorithm for the automatic configuration of algorithms;and filtering numerical CSPs using well-constrained subsystems.
We investigate soft open constraints. We generalize and unify classes of soft constraints and adapt them to the open setting. We give sufficient Conditions for generalized classes of decomposition-based and edit-based...
详细信息
ISBN:
(纸本)9783642042430
We investigate soft open constraints. We generalize and unify classes of soft constraints and adapt them to the open setting. We give sufficient Conditions for generalized classes of decomposition-based and edit-based soft constraints to be contractible. Finally, we outline a propagator for an open generalized edit-based Soft REGULAR constraint.
In most of the constraint-based approaches to planning, the problem is unfolded over a given number of steps. Because this Unfolded CSP encoding is very time mid memory consuming, we propose oil top of: the CNT framew...
详细信息
ISBN:
(纸本)9783642042430
In most of the constraint-based approaches to planning, the problem is unfolded over a given number of steps. Because this Unfolded CSP encoding is very time mid memory consuming, we propose oil top of: the CNT framework (constraint Networks on Timelines) a more efficient slice CSP encoding which allows only a limited number of steps to be considered at each step of the search.
Today's models for propagation-based constraint solvers require propagators as implementations of constraints to be at least contracting and monotonic. these models do not comply with reality: today's constrai...
详细信息
ISBN:
(纸本)9783642042430
Today's models for propagation-based constraint solvers require propagators as implementations of constraints to be at least contracting and monotonic. these models do not comply with reality: today's constraint, programming systems actually use non-monotonic propagators. this paper introduces the first realistic model of constraint propagation by assuming it propagator to be weakly monotonic (complying withthe constraint it implements). Weak monotonicity is shown to be the minimal property that guarantees constraint propagation to be sound and complete. the important insight is that weak monotonicity makes propagation in combination. with search well behaved. A case study suggests that non-monotonicity call be seen as all opportunity for more efficient propagation.
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.
We revisit the Interactive CSP framework (ICSP) and propose a, new: somewhat more general model, which we call Cost-Driven Interactive CSP (CICSP). First, we extend the value acquisition by a more general concept of c...
详细信息
ISBN:
(纸本)9783642042430
We revisit the Interactive CSP framework (ICSP) and propose a, new: somewhat more general model, which we call Cost-Driven Interactive CSP (CICSP). First, we extend the value acquisition by a more general concept of constraint relaxation. Second, we loosen the basic assumption of ICSP that "value acquisition is expensive" by introducing external cost functions of the constraint relaxation and the constraint propagation effort. We also propose a general INTERACTIVE RELAXATION algorithm template that. is designated for CICSP. the effectiveness of this approach is illustrated oil a real-life scenario from the Functional Test Generation problem domain.
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.
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.
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.
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.
暂无评论