We introduce a constraint-based framework for studying infinite qualitative simulations concerned with contingencies such as time, space, shape, size, abstracted into a finite set of qualitative relations. To define t...
详细信息
ISBN:
(纸本)3540462678
We introduce a constraint-based framework for studying infinite qualitative simulations concerned with contingencies such as time, space, shape, size, abstracted into a finite set of qualitative relations. To define the simulations we combine constraints that formalize the background knowledge concerned with qualitative reasoning with appropriate inter-state constraints that are formulated using linear temporal logic. We implemented this approach in a constraintprogramming system ((ECLPSe)-P-i) by drawing on the ideas from bounded model checking. the implementation became realistic only after several rounds of optimizations and experimentation with various heuristics. the resulting system allows us to test and modify the problem specifications in a straightforward way and to combine various knowledge aspects. To demonstrate the expressiveness and simplicity of this approach we discuss in detail two examples: a navigation problem and a simulation of juggling.
constraint Violation Minimization Problems arise when dealing with over-constrained CSPs. Unfortunately, experiments and practice show that they quickly become too large and too difficult to be optimally solved. In th...
详细信息
ISBN:
(纸本)3540652248
constraint Violation Minimization Problems arise when dealing with over-constrained CSPs. Unfortunately, experiments and practice show that they quickly become too large and too difficult to be optimally solved. In this context, multiple methods (limited tree search, heuristic or stochastic local search) are available to produce non-optimal, but good quality solutions, and thus to provide the user with anytime upper bounds of the problem optimum. On the other hand, few methods are available to produce anytime lower bounds of this optimum. In this paper, we explore some ways of producing such bounds. All of them are algorithmic variants of a Branch and Bound search. More specifically, we show that a new algorithm, resulting from a combination of the Russian Doll Search and Iterative Deepening algorithms, clearly outperforms five known algorithms and allows high lower bounds to be rapidly produced.
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.
We introduce the SOFTALLEQUAL global constraint. which maximizes the number of equalities holding between hairs of assignments to a set of variables. MO study the computational complexity of propagating this constrain...
详细信息
ISBN:
(纸本)9783540859574
We introduce the SOFTALLEQUAL global constraint. which maximizes the number of equalities holding between hairs of assignments to a set of variables. MO study the computational complexity of propagating this constraint, showing that it is intractable in general. Since maximizing the number of pairs of equally assigned variables ill a set is NP-hard. We propose three: ways of coping with NP-hardness Firstly, we develop a greedy linear-time algorithm to approximate the maximum number of equalities within a factor on. Secondly. we identify a tractable (polynomial) class for this constraint. thirdly;we identify a parameter based oil this class and show that the SOFTALLEQUAL constraint is fixed-parameter tractable with respect to this parameter.
Tractability results for structural subproblems have generally been considered for explicit relations listing the allowed assignments. In this paper we define a representation which allows us to express constraint rel...
详细信息
ISBN:
(纸本)3540462678
Tractability results for structural subproblems have generally been considered for explicit relations listing the allowed assignments. In this paper we define a representation which allows us to express constraint relations as either an explicit set of allowed labelings, or an explicit set of disallowed labelings, whichever is smaller. We demonstrate a new structural width parameter, which we call the interaction width, that when bounded allows us to carry over well known structural decompositions to this more concise representation. Our results naturally derive new structurally tractable classes for SAT.
this paper describes a new approach for solving disjunctive temporal problems such as the open shop and job shop scheduling domains. Much previous research in systematic search approaches for these problems has focuse...
详细信息
ISBN:
(纸本)9783642042430
this paper describes a new approach for solving disjunctive temporal problems such as the open shop and job shop scheduling domains. Much previous research in systematic search approaches for these problems has focused oil developing problem specific constraint propagators and ordering heuristics. Indeed, the common belief is that many of these problems are too difficult to solve without such domain specific models. We introduce a simple constraint model that combines a generic adaptive heuristic with naive propagation, and show that it often outperforms state-of-the-art solvers for both open shop and job shop problems.
We introduce a definition of constraint symmetry for soft CSPs, based on the definition of constraint symmetry for classical CSPs. We show that the constraint symmetry group of a soft CSP is a subgroup of that of an a...
详细信息
ISBN:
(纸本)9783540749691
We introduce a definition of constraint symmetry for soft CSPs, based on the definition of constraint symmetry for classical CSPs. We show that the constraint symmetry group of a soft CSP is a subgroup of that of an associated classical CSP instance. Where it is smaller, we can successfully exploit the additional symmetries using conditional symmetry breaking. We demonstrate, in a case-study of graph colouring, that eliminating the symmetry of the soft CSP combined with conditional symmetry breaking can lead to huge reductions in the search effort to find an optimal solution to the soft CSP.
thanks to its extended expressiveness, the quantified constraint satisfaction problem (QCSP) can be used to model problems that are difficult to express in the standard CSP formalism. this is only recently that the co...
详细信息
ISBN:
(纸本)3540462678
thanks to its extended expressiveness, the quantified constraint satisfaction problem (QCSP) can be used to model problems that are difficult to express in the standard CSP formalism. this is only recently that the constraint community got interested in QCSP and proposed algorithms to solve it. In this paper we propose BlockSolve, an algorithm for solving QCSPs that factorizes computations made in branches of the search tree. Instead of following the order of the variables in the quantification sequence, our technique searches for combinations of values for existential variables at the bottom of the tree that will work for (several) values of universal variables earlier in the sequence. An experimental study shows the good performance of BlockSolve compared to a state of the art QCSP solver.
We explore to what extent and how efficiently constraintprogramming can be used in the context of automated reasoning for modal logics. We encode modal satisfiability problems as constraint satisfaction problems with...
详细信息
ISBN:
(纸本)3540202021
We explore to what extent and how efficiently constraintprogramming can be used in the context of automated reasoning for modal logics. We encode modal satisfiability problems as constraint satisfaction problems with non-boolean domains, together with suitable constraints. Experiments show that the approach is very promising.
Scaling frequency and voltage in a coordinated manner is a promising way to reduce energy and power. we explore the use of dynamic frequency clocking within the datapath and datapath scheduling algorithms that can be ...
详细信息
暂无评论