Catálogo de publicaciones - libros

The French nuclear park comprises 58 nuclear reactors distributed through the national territory on 19 geographical sites. They must be repeatedly stopped, for refueling and maintenance. The scheduling of these outages has to comply with various constraints, regarding safety, maintenance logistic, and plant operation, whilst it must contribute to the producer profit maximization. This industrial problem appears to be a hard combinatorial problem that conventional methods used up to now by Electricité de France (mainly based on Mixed Integer Programming) fail to solve properly. We present in this paper a new approach for modeling and solving this problem, combining Constraint Programming (CP) and Local Search. CP is used to find solutions to the outage scheduling problem, while Local Search is used to improve solutions with respect to a heuristic cost criterion. It leads to find solutions as good as with the conventional approaches, but taking into account all the constraints and in very reduced computing time.

In this paper, we propose a new algorithm to establish Generalized Arc Consistency (GAC) on positive table constraints, i.e. constraints defined in extension by a set of allowed tuples. Our algorithm visits the lists of valid and allowed tuples in an alternative fashion when looking for a support (i.e. a tuple that is both allowed and valid). It is then able to jump over sequences of valid tuples containing no allowed tuple and over sequences of allowed tuples containing no valid tuple. Our approach, that can be easily grafted to any generic GAC algorithm, admits on some instances a behaviour quadratic in the arity of the constraints whereas classical approaches, i.e. approaches that focus on either valid or allowed tuples, admit an exponential behaviour. We show the effectiveness of this approach, both theoretically and experimentally.

This paper describes a complete and efficient solution to the stochastic allocation and scheduling for Multi-Processor System-on-Chip (MPSoC). Given a conditional task graph characterizing a target application and a target architecture with alternative memory and computation resources, we compute an allocation and schedule minimizing the expected value of communication cost, being the communication resources one of the major bottlenecks in modern MPSoCs. Our approach is based on the Logic Based Benders decomposition where the stochastic allocation is solved through an Integer Programming solver, while the scheduling problem with conditional activities is faced with Constraint Programming. The two solvers interact through no-goods. The original contributions of the approach appear both in the allocation and in the scheduling part. For the first, we propose an exact analytic formulation of the stochastic objective function based on the task graph analysis, while for the scheduling part we extend the timetable constraint for conditional activities. Experimental results show the effectiveness of the approach.

In previous work, a new approach called Open CSP (OCSP) was defined as a way of integrate information gathering and problem solving. Instead of collecting all variable values before CSP resolution starts, OCSP asks for values dynamically as required by the solving process, starting from possibly empty domains. This strategy permits to handle unbounded domains keeping completeness. However, current OCSP algorithms show a poor performance. For instance, the FO-Search algorithm uses a Backtracking and needs to solve the new problem from scratch every time a new value is acquired. In this paper we improve the original algorithm for the OCSP model. Our contribution is two-fold: we incorporate local consistency and we avoid solving subproblems already explored in previous steps. Moreover, these two contributions guarantee the completeness of the algorithm and they do not increase the number of values needed for finding a solution. We provide experimental results than confirm a significant speed-up on the original approach.

Inspired by AND/OR search spaces for graphical models recently introduced, we propose to augment Ordered Decision Diagrams with AND nodes, in order to capture function decomposition structure. This yields AND/OR multi-valued decision diagram (AOMDD) which compiles a constraint network into a canonical form that supports polynomial time queries such as solution counting, solution enumeration or equivalence of constraint networks. We provide a compilation algorithm based on Variable Elimination for assembling an AOMDD for a constraint network starting from the AOMDDs for its constraints. The algorithm uses the apply operator which combines two AOMDDs by a given operation. This guarantees the complexity upper bound for the compilation time and the size of the AOMDD to be exponential in the treewidth of the constraint graph, rather than pathwidth as is known for ordered binary decision diagrams (OBDDs).

Distributed computing is increasingly important at a time when the doubling of the number of transistors on a processor every 18 months no longer translates in a doubling of speed but instead a doubling of the number of cores. Unfortunately, it also places significant conceptual and implementation burden on programmers. This paper aims at addressing this challenge for constraint-based local search (CBLS), whose search procedures typically exhibit inherent parallelism stemming from multistart, restart, or population-based techniques whose benefits have been demonstrated both experimentally and theoretically. The paper presents abstractions that allows distributed CBLS programs to be close to their sequential and parallel counterparts, keeping the conceptual and implementation overhead of distributed computing minimal. A preliminary implementation in Comet exhibits significant speed-ups in constraint satisfaction and optimization applications. The implementation also scales well with the number of machines. Of particular interest is the observation that generic abstractions of CBLS and CP, such as models and solutions, and advanced control structures such as events and closures, play a fundamental role to keep the distance between sequential and distributed CBLS programs small. As a result, the abstractions directly apply to CP programs using multistarts or restarts procedures.

This paper presents high-level abstractions for nondeterministic search in C++ which provide the counterpart to advanced features found in recent constraint languages. The abstractions have several benefits: they explicitly highlight the nondeterministic nature of the code, provide a natural iterative style, simplify debugging, and are efficiently implementable using macros and continuations. Their efficiency is demonstrated by comparing their performance with the C++ library Gecode , both for programming search procedures and search engines.

An important issue for temporal planners is the ability to handle temporal uncertainty. Recent papers have addressed the question of how to tell whether a temporal network is Dynamically Controllable , i.e., whether the temporal requirements are feasible in the light of uncertain durations of some processes. Previous work has presented an O ( N ^5) algorithm for testing this property. Here, we introduce a new analysis of temporal cycles that leads to an O ( N ^4) algorithm.

Inter-block backtracking ( IBB ) computes all the solutions of sparse systems of non-linear equations over the reals. This algorithm, introduced in 1998 by Bliek et al., handles a system of equations previously decomposed into a set of (small) k × k sub-systems, called blocks. Partial solutions are computed in the different blocks and combined together to obtain the set of global solutions. When solutions inside blocks are computed with interval-based techniques, IBB can be viewed as a new interval-based algorithm for solving decomposed equation systems. Previous implementations used Ilog Solver and its IlcInterval library. The fact that this interval-based solver was more or less a black box implied several strong limitations. The new results described in this paper come from the integration of IBB with the interval-based library developed by the second author. This new library allows IBB to become reliable (no solution is lost) while still gaining several orders of magnitude w.r.t. solving the whole system. We compare several variants of IBB on a sample of benchmarks, which allows us to better understand the behavior of IBB . The main conclusion is that the use of an interval Newton operator inside blocks has the most positive impact on the robustness and performance of IBB . This modifies the influence of other features, such as intelligent backtracking and filtering strategies.

We extend the common depth-first backtrack search for constraint satisfaction problems with randomized variable and value selection. The resulting methods are applied to real-world instances of the tail assignment problem, a certain kind of airline planning problem. We analyze the performance impact of these extensions and, in order to exploit the improvements, add restarts to the search procedure. Finally computational results of the complete approach are discussed.