Catálogo de publicaciones - libros

The effects of combining search and modelling techniques can be complex and unpredictable, so guidelines are very important for the design and development of effective and robust solvers and models. A recently observed phenomenon is the negative effect of symmetry breaking constraints on local search performance. The reasons for this are poorly understood, and we attempt to shed light on the phenomenon by testing three conjectures: that the constraints create deep new local optima; that they can reduce the relative size of the basins of attraction of global optima; and that complex local search heuristics reduce their negative effects.

A cardinality constraint imposes that each value of a set V must be taken a certain number of times by a set of variables X, whereas an among constraint imposes that a certain number of variables of a set X must take a value in the set V.

This paper studies several combinations of among constraints and several conjunctions of among constraints and cardinality constraints. Some filtering algorithms are proposed and they are characterized when it is possible. Moreover, a weak form of Singleton arc consistency is considered. At last, it is shown how the global sequencing constraint and the global minimum distance constraint can be easily modeled by some conjunctions of cardinality and among constraints. Some results are also given for the global minimum distance constraint. They show that our study outperforms the existing constraint in ILOG Solver.

We identify a property of constraints called , and present an extremely simple randomized algorithm for solving smooth constraints. The complexity of the algorithm is much less than the lower bound for establishing path-consistency, and because smoothness is shown to be identical to connected row-convexity (CRC) for the case of binary constraints, the time and space complexity of solving CRC constraints is improved. Central to our algorithm is the relationship of smooth constraints to random walks on directed graphs. We also provide simple deterministic algorithms to test for the smoothness of a given CSP under given domain orderings of the variables. Finally, we show that some other known tractable constraint languages, like the set of implicational constraints, and the set of binary integer linear constraints, are special cases of smooth constraints, and can therefore be solved much more efficiently than the traditional time and space complexities attached with them.

In this paper, we present a method for solving Mixed Logical/ Integer Linear Programming (MLILP) problems that integrates a polynomial-time ILP solver for the special class of Unit-Two-Variable-Per-Inequality (unit TVPI or UTVPI) constraints of the form + ≤ , where , ∈ {-1, 0, 1}, into generic Boolean SAT solvers. In our approach the linear constraints are viewed as special literals and replaced by binary “indicator” variables to generate a pure logical problem. The resulting problem is subsequently solved using a SAT search procedure which invokes the linear UTVPI solver to incrementally check the consistency of the UTVPI constraints whenever any of the indicator variables are assigned to true. The linear UTVPI solver, on the other hand, can possibly pass or to the Boolean SAT solver. Checking the consistency of the UTVPI constraints incrementally enables the UTVPI solver to efficiently interact with the different components of the SAT solver. Additionally, several heuristics and encoding methods are proposed to accommodate the special circumstances of activating UTVPI constraints by the SAT solver. Empirical evidence is presented that demonstrates the advantages of our combined method for large problems.

An optimization problem arising in the design of optical fibre networks is discussed. A network contains client nodes, each installed on one or more SONET rings. A constraint programming model of the problem is described and compared with a mixed integer programming formulation. In the CP model the search is decomposed into two stages; first partially solving the problem by deciding how many rings each node should be on, and then making specific assignments of nodes to rings. The model includes implied constraints derived by considering optimal solutions to subproblems. In both the MIP and CP models, it is important to deal with the symmetry of the problem. In the CP model, two sources of symmetry are separated; one is eliminated dynamically during search and the other by assigning ranges rather than explicit values to one set of decision variables. The resulting CP model allows optimal solutions to be found easily for benchmark problems.

We present the tree-of-BDDs approach, a decomposition scheme for compiling configuration problems. Methods for minimum explanations and full interchangeable value sets detection are also given. Experiments show that the techniques presented here can drastically reduce the time and space requirements for interactive configurators.

Creating good integer programming formulations had, as a basic axiom, the rule “Find formulations with tighter linear relaxations”. This rule, while useful when using unsophisticated branch-and-bound codes,is insufficient when using state-of-the-art codes that understand and embed many of the obvious formulation improvements. As these optimization codes become more sophisticated it is important to have finer control over their operation. Modelers need to be even more creative in reformulating their integer programs in order to improve on the automatic reformulations of the optimization codes.

Hybrid algorithms combining local and systematic search often use nondeterminism in fundamentally different ways. They may differ in the strategy to explore the search tree and/or in how computation states are represented. This paper presents nondeterministic control structures to express a variety of hybrid search algorithms concisely and elegantly. These nondeterministic abstractions describe the search tree and are compiled in terms of first-class continuations. They are also parameterized by search controllers that are under user control and specify the state representation and the exploration strategy. The resulting search language is thus high-level, flexible, and directly extensible. The abstractions are illustrated on a jobshop scheduling algorithm that combines tabu search and a limited form of backtracking. Preliminary experimental results indicate that the control structures induce small, often negligible, overheads.

Integration of explanations into a CSP solver is a technique addressing difficult question . Moreover, explanations together with advanced search methods like directed backjumping can effectively cut off parts of the search tree and thus speed up the search.

In order to use explanations, propagation algorithms must provide some sort of reasons for their actions. For binary constraints it is mostly easy. In the case of global constraints computation of factual justifications can be tricky and/or computationally expensive.

This paper shows how to effectively compute explanations for the unary resource constraint. The explanations are computed in a lazy way. The technique is experimentally demonstrated on job-shop benchmark problems. The following propagation algorithms are considered: edge-finding, not-first/not-last and detectable precedences. Speed of these filtering algorithms and speed of the explanation computation is the main interest.