Catálogo de publicaciones - libros

The constraint takes two sets of variables and such that ||=|| and assigns values to them such that the multiset of values assigned to the variables in is equal to the multiset of values assigned to the variables in . In this paper we extend the constraint in a GCC-like manner by adding cardinality requirements on the values. That is, for each value we have a lower and upper bound on the number of variables that can be assigned this value. We show an algorithm that achieves arc-consistency for this constraint and a faster algorithm that achieves bound-consistency for a restricted case of it.

We propose to use bilattice as a constraint valuation structure in order to represent truth and belief at the same time. A bilattice is a set which owns two lattices orderings. They have been used in Artificial Intelligence in order to model incomplete information. We present a framework for Bilattice-valued Constraint Programming which allows to represent incomplete or conflicting information and to combine constraints with a set of operators. It allows to model a variety of situation such as open constraints and the integration of machine learning into constraint programming, reconciliation of divergent opinions in distributed systems or constraint modules in a software engineering perspective.

We introduce a notion of equally constrained variables of a constraint network. We propose a method of pruning that uses the notion. We combine the proposed method of pruning with FC-CBJ and call the resulting algorithm FC-CBJ-EQ. Our experimental results show that FC-CBJ-EQ outperforms FC-CBJ on constraint networks that encode randomly generated instances of graph -coloring and of the subgraph isomorphism problems.

For constraint satisfaction problems (CSPs), Haralick & Elliott [1] introduced the Fail-First Principle and defined in it terms of minimizing branch depth. By devising a range of variable ordering heuristics, each in turn trying harder to fail first, Smith & Grant [2] showed that adherence to this strategy does not guarantee reduction in search effort. The present work builds on Smith & Grant. It benefits from the development of a new framework for characterizing heuristic performance that defines two , one concerned with enhancing the likelihood of correctly extending a partial solution, the other with minimizing the effort to prove insolubility. The Fail-First Principle can be restated as calling for adherence to the second, policy, while discounting the other, policy. Our work corrects some deficiencies in the work of Smith & Grant, and goes on to confirm their finding that the Fail-First Principle, as originally defined, is insufficient. We then show that adherence to the fail-first policy must be measured in terms of size of insoluble subtrees, not branch depth. We also show that for soluble problems, both policies must be considered in evaluating heuristic performance. Hence, even in its proper form the Fail-First Principle is insufficient. We also show that the “FF” series of heuristics devised by Smith & Grant is a powerful tool for evaluating heuristic performance, including the subtle relations between heuristic features and adherence to a policy.

We propose an improved restart strategy for randomized backtrack search, and evaluate its performance by comparing to other heuristic and stochastic search techniques for solving random problems and a tight real-world resource allocation problem. The restart strategy proposed by Gomes et al. [1] requires the specification of a cutoff value determined from an overall profile of the cost of search for solving the problem. When no such profile is known, the cutoff value is chosen by trial-and-error. The Randomization and Geometric Restart (RGR) proposed by Walsh does not rely on a cost profile but determines the cutoff value as a function of a constant parameter and the number of variables in the problem [2]. Unlike these strategies, which have fixed restart schedules, our technique (RDGR) dynamically adapts the value of the cutoff parameter to the results of the search process. Our experiments investigate the behavior of these techniques using the cumulative distribution of the solutions, over different run-time durations, values of the cutoff, and problem types. We show that distinguishing between solvable and over-constrained problem instances yields new insights on the relative performance of the search techniques tested. We propose to use this characterization as a basis for building new strategies of cooperative, hybrid search.

We consider Distributed Constraint Satisfaction Problems (DisCSP) when control of variables and constraints is distributed among a set of agents. This paper presents a distributed version of the centralized BackJumping algorithm, called the – algorithm. The advantage is twofold: inherits the strength of synchronous algorithms that enables it to easily combine with a powerful dynamic ordering of variables and values, and still it maintains some level of autonomy for the agents. Experimental results show that outperforms the and algorithms by a factor of orders of magnitude on hard instances of randomly generated DisCSPs.

In this paper we develop a localized value-ordering heuristic for distributed resource allocation problems. We show how this value ordering heuristics can be used to achieve desirable properties (increased effectiveness, or better allocations). The specific distributed resource allocation problem that we consider is sensor allocation in sensor networks, and the algorithmic skeleton that we use to experiment this heuristic is the distributed breakout algorithm.

We compare this technique with the standard DBA and with another value-ordering heuristic [10] and see from the experimental results that it significantly outperforms both of them in terms of the number of cycles required to solve the problem (and therefore improvements in terms of communication and time requirements), especially when the problems are difficult. The resulting algorithm is also able to solve a higher percentage of the test problems.

We show that a simple variation of this technique exhibits an interesting competition behavior that could be used to achieve higher quality allocations of the resource pool. Moreover, combinations of the two methods are possible, leading to interesting results.

Finally, we note that this heuristic is domain, but not algorithm specific (meaning that it could most likely give good results in conjunction with other DisCSP algorithms as well).

constraint satisfaction, distributed AI, problem solving

We introduce a framework for studying and solving a class of CSP formulations. The framework allows constraints to be expressed as linear and non-linear equations, then compiles them into SAT instances via Boolean logic circuits. While in general reduction to SAT may lead to the loss of structure, we specifically detect several types of structure in high-level input and use them in compilation. Linearity is preserved by the use of pseudo-Boolean (PB) constraints in conjunction with a 0-1 ILP solver that extends common SAT-solving techniques. Symmetries are detected in high-level constraints by solving the graph automorphism problem on parse trees. Symmetry-breaking predicates are added during compilation. Our system generalizes earlier work on symmetries in SAT and 0-1 ILP problems. Empirical evaluation is performed on instances of the social golfers and Hamming code generation problems. We show substantial speedups with symmetry-breaking, especially on unsatisfiable instances. In general, our runtimes with the specialized 0-1 ILP solver Pueblo are competitive with results recently reported for ILOG Solver.

We propose four new structural decomposition techniques for Constraint Satisfaction Problems. We compare these four techniques both theoretically and experimentally with hinge decomposition and hypertree decomposition. Our experiments show that one of our techniques offers the best trade-off between the computational cost of the decomposition and the width of the resulting decomposition tree.

We study the problem of finding two solutions to a constraint satisfaction problem which differ on the assignment of as many variables as possible – the problem for CSPs – a problem which can, among other things, be seen as a domain independent way of quantifying “ignorance.” The first algorithm we present is an microstructure based algorithm for 2-SAT, improving the previously best known algorithm for this problem, which has a running time of . We also give algorithms based on enumeration techniques for solving both -SAT, and the general (,)-CSP, the first non-trivial algorithms for these problems. The main results here are that if we can solve -SAT in and (,)-CSP in , then the corresponding Max Hamming problems can be solved in and , respectively.