Catálogo de publicaciones - libros

We perform an in-depth empirical study of runtime distributions associated with a continuum of problem formulations for QWH-10 with 90% holes defined between the points where a formulation is entirely specified in terms of binary inequality constraints to models specified using an increasing number of AllDifferent global constraints [4]. For each model we study a variety of variable and value ordering heuristics. We compare their runtime distributions against runtime distributions where any mistakes made in search are refuted optimally [2], and make the following observations:

This paper deals with methods exploiting tree-decomposition approaches for solving constraint networks. We consider here the practical efficiency of these approaches by defining five classes of variable orders more and more dynamic which guarantee time complexity bounds from O ( exp ( w +1)) to O ( exp (2( w + k ))), with w the ”tree-width” of a CSP and k a constant. Finally, we assess practically their relevance.

In this paper we show that the clique concept can be exploited in order to solve Max-CSP. We present a clique inference process which leads to construct linear systems useful for computing new lower bounds. The clique inference process is introduced in the PFC-MPRDAC[5] algorithm and the obtained algorithm is called PFC-MPRDAC+CBB (CBB for Clique Based Bound). The carried out experiments have shown that PFC-MPRDAC+CBB leads to obtain very encouraging results.

Global constraints are an important tool in the constraint toolkit. Unfortunately, whilst it is usually easy to specify when a global constraint holds, it is often difficult to build a good propagator. One promising direction is to specify global constraints via grammars or automata. For example, the Regular constraint [1] permits us to specify a wide range of global constraints by means of a DFA accepting a regular language, and to propagate this constraint specification efficiently and effectively. More precisely, the Regular constraint ensures that the values taken by a sequence of variables form a string accepted by the DFA. In this paper, we consider how to propagate such grammar constraints and a number of extensions.

The coordinated management of inter-dependent plans or schedules belonging to different agents is a complex, real-world problem arising in diverse domains such as disaster rescue, small-team reconnaissance, and security patrolling. The problem is inherently a distributed one; no single agent has a global view and must make local scheduling decisions through collaboration with other agents to ensure a high quality global schedule. A key step towards addressing this problem is to devise appropriate distributed representations. The Coordinators Task Analysis Environmental Modeling and Simulation ( C_tæms ) language is a representation that was jointly designed by several multi-agent systems researchers explicitly for multi-agent task scheduling problems [1,2,3,4]. C_tæms is an extremely challenging class of scheduling problem which is able to model the distributed aspects of the problem.

Interactive configuration is the process of assisting a user in selecting values for parameters that respect given constraints. Inspired by the increasing demand for the real-time configuration in Supply Chain Management, we apply a compilation approach to the problem of interactive distributed configuration where the user options depend on constraints fragmented over a number of different locations connected through a network. We formalize the problem, suggest a solution approach based on an asynchronous compilation scheme, and perform experimental verification.

Dynamic Backtracking ( DBT ) is a well known algorithm for solving Constraint Satisfaction Problems. In DBT , variables are allowed to keep their assignment during backjump, if they are compatible with the set of eliminating explanations. A previous study has shown that when DBT is combined with variable ordering heuristics it performs poorly compared to standard Conflict-directed Backjumping ( CBJ )[1]. The special feature of DBT , keeping valid elimination explanations during backtracking, can be used for generating a new class of ordering heuristics. In the proposed algorithm, the order of already assigned variables can be changed. Consequently, the new class of algorithms is termed Retroactive DBT . In the proposed algorithm, the newly assigned variable can be moved to a position in front of assigned variables with larger domains and as a result prune the search space more effectively. The experimental results presented in this paper show an advantage of the new class of heuristics and algorithms over standard DBT and over CBJ. All algorithms tested were combined with forward-checking and used a Min-Domain heuristic.