the Traveling Tournament Problem is a sports timetabling problem that abstracts two issues in creating timetables: home/away pattern feasibility and team travel. Instances of this problem seem to be very difficult eve...
详细信息
Applying GAC on conjunctions of constraints can lead to more powerful pruning [1].We show that there exists a simple heuristic for deciding which constraints might be useful to conjoin. the result is a useful automati...
详细信息
We investigate techniques that detect, dynamically during search, undeclared symmetries in the form of interchangeability (Freuder’91) in constraint Satisfaction Problems, withthe long-term goal of drawing ...
ISBN:
(纸本)3540428631
We investigate techniques that detect, dynamically during search, undeclared symmetries in the form of interchangeability (Freuder’91) in constraint Satisfaction Problems, withthe long-term goal of drawing a compact landscape of the solution space of a given CSP instance. As a first step towards our goal, we propose a new algorithm for dynamically computing interchangeability during backtrack search and demonstrate how it enhances the performance of search.
Adding constraints to a basic CSP model can significantly reduce search,e.g. for Golomb rulers [6]. the generation process is usually performed by hand, although some recent work has focused on automatically generatin...
ISBN:
(纸本)3540428631
Adding constraints to a basic CSP model can significantly reduce search,e.g. for Golomb rulers [6]. the generation process is usually performed by hand, although some recent work has focused on automatically generating symmetry breaking constraints [4]and (less so)on generating implied constraints [5]. We describe an approach to generating implied,symmetry breaking and specialisation constraints and apply this technique to quasigroup construction [10].
Configuration tasks are an important application area in engineering design. the proposed solving techniques use either a constraint based framework or a logic-based approach. We propose a methodology to obtains desir...
详细信息
A constraint satisfaction problem is defined by a set of variables associated to domains,and a set of constraints on these variables. Solving a constraint satisfaction problem consists in finding assignments of all va...
ISBN:
(纸本)3540428631
A constraint satisfaction problem is defined by a set of variables associated to domains,and a set of constraints on these variables. Solving a constraint satisfaction problem consists in finding assignments of all variables that satisfy all constraints. Since this problem is NP-hard,constraint propagation has been designed to struggle against the combinatorial explosion of brute-force search by pruning domains before enumeration. Filtering algorithms enforcing consistency properties [8]are the most well-known techniques for constraint propagation.
In recent years, there is an increasing interest in modeling and reasoning about complex dynamic systems for tasks such as design, configuration, simulation and diagnosis of technical devices. these tasks, however, re...
ISBN:
(纸本)3540428631
In recent years, there is an increasing interest in modeling and reasoning about complex dynamic systems for tasks such as design, configuration, simulation and diagnosis of technical devices. these tasks, however, require expensive reasoning methods, therefore one of the main issues in real applications is how to reduce the computational cost of reasoning about dynamic models.
the paper presents propagation rules that are common to the minimum constraint family and to the number of distinct values constraint family. One practical interest of the paper is to describe an implementation of the...
详细信息
In the scope of distributed constraint reasoning, the main algorithms presented so far have a feature in common: the addition of links between previously unrelated agents, before or during search. Our work presents a ...
详细信息
In this paper we have modeled tradeoffs in constraint-based configuration as additional constraints, and begun to study the issues involved in generating and evaluating such tradeoffs. We describe our basic approach i...
详细信息
暂无评论