Catálogo de publicaciones - libros

The constraint satisfaction problem is in general NP-hard. As such, our aim is to identify tractable classes of constraint satisfaction problem instances (CSPs). Tractable classes of CSPs are normally described by limiting either the structure or the language of the CSPs. Structural decomposition methods identify CSPs whose reduction to the acyclic class is bound by a polynomial. These structural decompositions have been a very useful way to identify large tractable classes. However, these decomposition techniques have not yet been applied to relational tractability results. In this paper we introduce the notion of a typed guarded decomposition as a way to generalize the structural decompositions. We develop a no-promise algorithm which derives large new tractable classes of CSPs that are not describable as purely structural nor purely relational classes.

Constraint Satisfaction Problems and Propositional Satisfiability, are frameworks widely used to represent and solve combinatorial problems. A concept of primary importance in both frameworks is that of constraint propagation. In this paper we study and compare the amount of propagation that can be achieved, using various methods, when translating a problem from one framework into another. Our results complement, extend, and tie together recent similar studies. We provide insight as to which translation is preferable, with respect to the strength of propagation in the original problem and the encodings.

The paper introduces the MST ( G , T , W ) constraint, which is specified on two graph variables G and T and a vector W of scalar variables. The constraint is satisfied if T is a minimum spanning tree of G , where the edge weights are specified by the entries of W . We develop algorithms that filter the domains of all variables to bound consistency.

Algorithm selection, algorithm portfolios, and randomized restarts, can profit from a probabilistic model of algorithm run-time, to be estimated from data gathered by solving a set of experiments. Censored sampling offers a principled way of reducing this initial training time. We study the trade-off between training time and model precision by varying the censoring threshold, and analyzing the consequent impact on the performance of an optimal restart strategy, based on an estimated model of runtime distribution. We present experiments with a SAT solver on a graph-coloring benchmark. Due to the “heavy-tailed” runtime distribution, a modest censoring can already reduce training time by a few orders of magnitudes. The nature of the optimization process underlying the restart strategy renders its performance surprisingly robust, also to more aggressive censoring.

Efficient constraint propagation is crucial to any constraint solver. We show that watched literals , already a great success in the satisfiability community, can be used to provide highly efficient implementations of constraint propagators. We describe three important aspects of watched literals as we apply them to constraints, and how they are implemented in the Minion constraint solver. We show three successful applications of to constraint propagators: the sum of Boolean variables; GAC for the ‘element’ constraint; and GAC for the ‘table’ constraint.

We propose a branch and prune algorithm that is able to compute inner and outer approximations of the solution set of an existentially quantified constraint where existential parameters are shared between several equations. While other techniques that handle such constraints need some preliminary formal simplification of the problem or only work on simpler special cases, our algorithm is the first pure numerical algorithm that can approximate the solution set of such constraints in the general case. Hence this new algorithm allows computing inner approximations that were out of reach until today.

Machine learning can be used to build models that predict the run-time of search algorithms for hard combinatorial problems. Such empirical hardness models have previously been studied for complete, deterministic search algorithms. In this work, we demonstrate that such models can also make surprisingly accurate predictions of the run-time distributions of incomplete and randomized search methods, such as stochastic local search algorithms. We also show for the first time how information about an algorithm’s parameter settings can be incorporated into a model, and how such models can be used to automatically adjust the algorithm’s parameters on a per-instance basis in order to optimize its performance. Empirical results for Novelty^ +  and SAPS on structured and unstructured SAT instances show very good predictive performance and significant speedups of our automatically determined parameter settings when compared to the default and best fixed distribution-specific parameter settings.

In recent years, dynamic local search (DLS) clause weighting algorithms have emerged as the local search state-of-the-art for solving propositional satisfiability problems. However, most DLS algorithms require the tuning of domain dependent parameters before their performance becomes competitive. If manual parameter tuning is impractical then various mechanisms have been developed that can automatically adjust a parameter value during the search. To date, the most effective adaptive clause weighting algorithm is RSAPS. However, RSAPS is unable to convincingly outperform the best non-weighting adaptive algorithm AdaptNovelty^ + , even though manually tuned clause weighting algorithms can routinely outperform the Novelty^ +  heuristic on which AdaptNovelty^ +  is based. In this study we introduce R+DDFW^ + , an enhanced version of the DDFW clause weighting algorithm developed in 2005, that not only adapts the total amount of weight according to the degree of stagnation in the search, but also incorporates the latest resolution-based preprocessing approach used by the winner of the 2005 SAT competition (R+ AdaptNovelty^ + ). In an empirical study we show R+DDFW^ +  improves on DDFW and outperforms the other leading adaptive (R+Adapt-Novelty^ + , R+RSAPS) and non-adaptive (R+G^2WSAT) local search solvers over a range of random and structured benchmark problems.

Since electromagnetic waves are strongly attenuated inside the water, the satellite based global positioning system (GPS) cannot be used by submarine robots except at the surface of the water. This paper shows that the localization problem in deep water can often be cast into a continuous constraints satisfaction problem where interval constraints propagation algorithms are particularly efficient. The efficiency of the resulting propagation methods is illustrated on the localization of a submarine robot, named Redermor . The experiments have been collected by the GESMA (Groupe d’Etude Sous-Marine de l’Atlantique) in the Douarnenez bay, in Brittany.

We study a family of problems, called Maximum Solution , where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables subject to a set of constraints. This problem is closely related to Integer Linear Programming .When the domain is Boolean (i.e. restricted to {0,1}), the maximum solution problem is identical to the well-studied Max Ones problem, and the approximability is completely understood for all restrictions on the underlying constraints. We continue this line of research by considering domains containing more than two elements. We present two main results: a complete classification for the approximability of all maximal constraint languages, and a complete classification of the approximability of the problem when the set of allowed constraints contains all permutation constraints.Our results are proved by using algebraic results from clone theory and the results indicates that this approach is very useful for classifying the approximability of certain optimisation problems.