Catálogo de publicaciones - libros

In this paper, we investigate how an IA network can be effectively encoded into the SAT domain. We propose two basic approaches to modelling an IA network as a CSP: one represents the relations between intervals as variables and the other represents the relations between end-points of intervals as variables. By combining these two approaches with three different SAT encoding schemes, we produced six encoding schemes for converting IA to SAT. These encodings were empirically studied using randomly generated IA problems of sizes ranging from 20 to 100 nodes. A general conclusion we draw from these experimental results is that encoding IA into SAT produces better results than existing approaches. Further, we observe that the phase transition region maps directly from the IA encoding to each SAT encoding, but, surprisingly, the location of the hard region varies according to the encoding scheme. Our results also show a fixed performance ranking order over the various encoding schemes.

In the last decades, the Satisfiability and Constraint Satisfaction Problem frameworks were extended to integrate aspects such as uncertainties, partial observabilities, or uncontrollabilities. The resulting formalisms, including Quantified Boolean Formulas (QBF), Quantified CSP (QCSP), Stochastic SAT (SSAT), or Stochastic CSP (SCSP), still rely on networks of local functions defining specific graphical models , but they involve queries defined by sequences of distinct elimination operators (∃ and ∀ for QBF and QCSP, max and + for SSAT and SCSP) preventing variables from being considered in an arbitrary order when the problem is solved (be it by tree search or by variable elimination). In this paper, we show that it is possible to take advantage of the actual structure of such multi-operator queries to bring to light new ordering freedoms. This leads to an improved constrained induced-width and doing so to possible exponential gains in complexity. This analysis is performed in a generic semiring-based algebraic framework that makes it applicable to various formalisms. It is related with the quantifier tree approach recently proposed for QBF but it is much more general and gives theoretical bases to observed experimental gains.

Symmetries are one of the difficulties constraint programming users have to deal with. One way to get rid of symmetries is to add lex constraints. However, it can adversely affect the efficiency of a tree search method if the lex constraints remove the solution that would have been found at the first place. We propose to use an alternative filtering algorithm which does not exclude the first solution. We present both a theoretical analysis and some experimental evidence that it is as efficient as lex constraints. We also show that its efficiency does not depend much on the variable ordering used in the tree search. Last, we show that it can prune more nodes than the SBDS method.

We introduce the SomeDifferent constraint as a generalization of AllDifferent . SomeDifferent requires that values assigned to some pairs of variables will be different. It has many practical applications. For example, in workforce management, it may enforce the requirement that the same worker is not assigned to two jobs which are overlapping in time. Propagation of the constraint for hyper-arc consistency is NP hard. We present a propagation algorithm with worst case time complexity O( n ^3 β ^ n ) where n is the number of variables and β ≈3.5 (ignoring a trivial dependence on the representation of the domains). We also elaborate on several heuristics which greatly reduce the algorithm’s running time in practice. We provide experimental results, obtained on a real-world workforce management problem and on synthetic data, which demonstrate the feasibility of our approach.

Many important combinatorial optimization problems can be expressed as constraint satisfaction problems with soft constraints . When problems are too difficult to be solved exactly, approximation methods become the best option. Mini-bucket Elimination (MBE) is a well known approximation method for combinatorial optimization problems. It has a control parameter z that allow us to trade time and space for accuracy. In practice, it is the space and not the time that limits the execution with high values of z . In this paper we introduce a new propagation phase that MBE should execute at each bucket. The purpose of this propagation is to jointly process as much information as possible. As a consequence, the undesirable lose of accuracy caused by MBE when splitting functions into different mini-buckets is minimized. We demonstrate our approach in scheduling , combinatorial auction and max-clique problems, where the resulting algorithm MBE ^ p gives important percentage increments of the lower bound (typically 50% and up to 1566%) with only doubling the cpu time.

The constraint satisfaction problem can be solved in polynomial time for instances where certain parameters (e.g., the treewidth of primal graphs) are bounded. However, there is a trade-off between generality and performance: larger bounds on the parameters yield worse time complexities. It is desirable to pay for more generality only by a constant factor in the running time, not by a larger degree of the polynomial. Algorithms with such a uniform polynomial time complexity are known as fixed-parameter algorithms. In this paper we determine whether or not fixed-parameter algorithms for constraint satisfaction exist, considering all possible combinations of the following parameters: the treewidth of primal graphs, the treewidth of dual graphs, the treewidth of incidence graphs, the domain size, the maximum arity of constraints, and the maximum size of overlaps of constraint scopes. The negative cases are subject to the complexity theoretic assumption FPT ≠ W[1] which is the parameterized analog to P ≠ NP. For the positive cases we provide an effective fixed-parameter algorithm which is based on dynamic programming on “nice” tree decompositions.

In this paper we investigate the use of preprocessing when solving Quantified Boolean Formulas (QBF). Many different problems can be efficiently encoded as QBF instances, and there has been a great deal of recent interest and progress in solving such instances efficiently. Ideas from QBF have also started to migrate to CSP with the exploration of Quantified CSPs which offer an intriguing increase in representational power over traditional CSPs. Here we show that QBF instances can be simplified using techniques related to those used for preprocessing SAT. These simplifications can be performed in polynomial time, and are used to preprocess the instance prior to invoking a worst case exponential algorithm to solve it. We develop a method for preprocessing QBF instances that is empirically very effective. That is, the preprocessed formulas can be solved significantly faster, even when we account for the time required to perform the preprocessing. Our method significantly improves the efficiency of a range of state-of-the-art QBF solvers. Furthermore, our method is able to completely solve some instances just by preprocessing, including some instances that to our knowledge have never been solved before by any QBF solver.

By introducing the Regular Membership Constraint, Gilles Pesant pioneered the idea of basing constraints on formal languages. The paper presented here is highly motivated by this work, taking the obvious next step, namely to investigate constraints based on grammars higher up in the Chomsky hierarchy. We devise an arc-consistency algorithm for context-free grammars, investigate when logic combinations of grammar constraints are tractable, show how to exploit non-constant size grammars and reorderings of languages, and study where the boundaries run between regular, context-free, and context-sensitive grammar filtering.

The problem of finding a graceful labelling of a graph, or proving that the graph is not graceful, has previously been modelled as a CSP. A new and much faster CSP model of the problem is presented, with several new results for graphs whose gracefulness was previously unknown. Several classes of graph that are conjectured to be graceful only for small instances are investigated: after a certain size, it appears that for some of these classes the search to prove that there is no graceful labelling is essentially the same for each successive instance. The possibility of constructing a proof of the conjecture based on the search is discussed.

The max k -armed bandit problem is a recently-introduced online optimization problem with practical applications to heuristic search. Given a set of k slot machines, each yielding payoff from a fixed (but unknown) distribution, we wish to allocate trials to the machines so as to maximize the maximum payoff received over a series of n trials. Previous work on the max k -armed bandit problem has assumed that payoffs are drawn from generalized extreme value (GEV) distributions. In this paper we present a simple algorithm, based on an algorithm for the classical k -armed bandit problem, that solves the max k -armed bandit problem effectively without making strong distributional assumptions. We demonstrate the effectiveness of our approach by applying it to the task of selecting among priority dispatching rules for the resource-constrained project scheduling problem with maximal time lags (RCPSP/max).