Catálogo de publicaciones - libros

Visualization is often invaluable to understand the behavior of optimization algorithms, identify their bottlenecks or pathological behaviors, and suggest remedies. Yet developing visualizations is a tedious activity requiring significant time and expertise. This paper presents a framework for the visualization of constraint-based local search (CBLS). Given a high-level model and a declarative visualization specification, the CBLS visualizer systematically produces animations to visualize constraints and objectives, violations, and conflicts, as well as the temporal behavior of these measures. The visualization specification is composed of a triple (,,) indicating what to display, where, and how. The visualizer architecture is compositional and extensible, and focuses almost exclusively on static aspects, the dynamic aspects being automated by invariants. The paper highlights various functionalities of the visualizer and describes a blueprint for its implementation.

We consider soft constraint problems where some of the preferences may be unspecified. This models, for example, situations with several agents providing the data, or with possible privacy issues. In this context, we study how to find an optimal solution without having to wait for all the preferences. In particular, we define an algorithm to find a solution which is necessarily optimal, that is, optimal no matter what the missing data will be, with the aim to ask the user to reveal as few preferences as possible. Experimental results show that in many cases a necessarily optimal solution can be found without eliciting too many preferences.

Computing the minimal network (or minimal CSP) representation of a given set of constraints over the Point Algebra (PA) is a fundamental reasoning problem. In this paper we propose a new approach to solving this task which exploits the timegraph representation of a CSP over PA. A timegraph is a graph partitioned into a set of chains on which the search is supported by a metagraph data structure. We introduce a new algorithm that, by making a particular closure of the metagraph, extends the timegraph with information that supports the derivation of the strongest implied constraint between any pair of point variables in constant time. The extended timegraph can be used as a representation of the minimal CSP. We also compare our method and known techniques for computing minimal CSPs over PA. For CSPs that are sparse or exhibit chain structure, our approach has a better worst-case time complexity. Moreover, an experimental analysis indicates that the performance improvements of our approach are practically very significant. This is the case especially for CSPs with a chain structure, but also for randomly generated (both sparse and dense) CSPs.

In this paper, a new form of explanation and recovery technique for the unsatisfiability of discrete CSPs is introduced. Whereas most approaches amount to providing users with a minimal number of constraints that should be dropped in order to recover satisfiability, a finer-grained alternative technique is introduced. It allows the user to reason both at the constraints and tuples levels by exhibiting both problematic constraints and tuples of values that would allow satisfiability to be recovered if they were not forbidden. To this end, the Minimal Set of Unsatisfiable Tuples (MUST) concept is introduced. Its formal relationships with Minimal Unsatisfiable Cores (MUCs) are investigated. Interestingly, a concept of shared forbidden tuples is derived. Allowing any such tuple makes the corresponding MUC become satisfiable. From a practical point of view, a two-step approach to the explanation and recovery of unsatisfiable CSPs is proposed. First, a recent approach proposed by Hemery ’s is used to locate a MUC. Second, a specific SAT encoding of a MUC allows MUSTs to be computed by taking advantage of the best current technique to locate Minimally Unsatisfiable Sub-formulas (MUSes) of Boolean formulas. Interestingly enough, shared tuples coincide with protected clauses, which are one of the keys to the efficiency of this SAT-related technique. Finally, the feasibility of the approach is illustrated through extensive experimental results.

Stochastic Local Search (SLS) is a simple and effective paradigm for attacking a variety of Combinatorial (Optimization) Problems (COP). However, it is often non-trivial to get good results from an SLS; the designer of an SLS needs to undertake a laborious and ad-hoc algorithm tuning and re-design process for a particular COP. There are two general approaches. Black-box approach treats the SLS as a black-box in tuning the SLS parameters. White-box approach takes advantage of humans to observe the SLS in the tuning and SLS re-design. In this paper, we develop an integrated white+black box approach with extensive use of visualization (white-box) and factorial design (black-box) for tuning, and more importantly, for designing arbitrary SLS algorithms. Our integrated approach combines the strengths of white-box and black-box approaches and produces better results than either alone. We demonstrate an effective tool using the integrated white+black box approach to design and tune variants of Robust Tabu Search (Ro-TS) for Quadratic Assignment Problem (QAP).

The techniques for making decisions, i.e., branching, play a central role in complete methods for solving structured CSP instances. In practice, there are cases when SAT solvers benefit from limiting the set of variables the solver is allowed to branch on to so called input variables. Theoretically, however, restricting branching to input variables implies a super-polynomial increase in the length of the optimal proofs for DPLL (without clause learning), and thus input-restricted DPLL cannot polynomially simulate DPLL. In this paper we settle the case of DPLL with clause learning. Surprisingly, even with unlimited restarts, input-restricted clause learning DPLL cannot simulate DPLL (even without clause learning). The opposite also holds, and hence DPLL and input-restricted clause learning DPLL are polynomially incomparable. Additionally, we analyse the effect of input-restricted branching on clause learning solvers in practice with various structural real-world benchmarks.

This paper deals with the problem of solving efficiently structured CSPs. It is well known that (hyper)tree-decompositions offer the best approaches from a theoretical viewpoint, but from the practical viewpoint, these methods do not offer efficient algorithms. Therefore, we introduce here a framework founded on coverings of CSP by acyclic hypergraphs. We study their properties and relations, and evaluate theoretically their interest with respect to the solving of structured problems. This framework does not define a new decomposition, but makes easier a dynamic management of the CSP structure during the search, and so an exploitation of dynamic variables ordering heuristics in the solving method. Thus, we provide a new complexity result which outperforms significantly the previous one given in the literature about heuristics for solving a decomposed problem. Finally, we present experimental results to assess the practical interest of these notions.

We present an algorithm for compressing table constraints representing allowed or disallowed tuples. This type of constraint is used for example in configuration problems, where the satisfying tuples are read from a database. The arity of these constraints may be large. A generic GAC algorithm for such a constraint requires time exponential in the arity of the constraint to maintain GAC, but Bessière and Régin showed in [1] that for the case of allowed tuples, GAC can be enforced in time proportional to the number of allowed tuples, using the algorithm .

We introduce a more compact representation for a set of tuples, which allows a potentially exponential reduction in the space needed to represent the satisfying tuples and exponential reduction in the time needed to enforce GAC. We show that this representation can be constructed from a decision tree that represents the original tuples and demonstrate that it does in practice produce a significantly shorter description of the constraint. We also show that this representation can be efficiently used in existing algorithms and can be used to improve further. Finally, we show that this method can be used to improve the complexity of enforcing GAC on a table constraint defined in terms of forbidden tuples.

Most of efficient WCSP solving methods are based on arc consistency notion used to transform a WCSP into an equivalent one easier to solve. There are several forms of arc consistency : AC* [9], DAC* [8], FDAC* [8], EDAC* [4]. Recently, an Optimal Soft Arc Consistency (OSAC) was proposed [2]. But this technique requires much computing time since it is based on a large linear program. We propose in this work a new valid transformation based on modeling of the WCSP as a linear program easier to solve than the computing of OSAC. Preliminary experiments on random and structured problems are presented, showing the advantage of our technique.

While incremental propagation for global constraints is recognized to be important, little research has been devoted to how propagator-centered constraint programming systems should support incremental propagation. This paper introduces advisors as a simple and efficient, yet widely applicable method for supporting incremental propagation in a propagator-centered setting. The paper presents how advisors can be used for achieving different forms of incrementality and evaluates cost and benefit for several global constraints.