Catálogo de publicaciones - libros

Plant PowerOps (PPO) [9] is a new ILOG product, based on business rules and optimization technology, dedicated to production planning and detailed scheduling for manufacturing. This paper describes how PPO integrates a rule based system with the optimization engines and the graphical user interface. The integration proposed is motivated by the need to allow business users to manage unexpected changes in their environment. It provides a flexible interface for configuring, maintaining and tuning the system and for managing optimization scenarios. The proposed approach is discussed via several use cases we encountered in practice in supply chain management. Nevertheless, we believe that most of the ideas described in this paper apply in almost any area of optimization application.

Embedded systems are everywhere: from alarm clocks to PDAs, from mobile phones to cars, almost all the devices we use are controlled by embedded systems. Over 99% of the microprocessors produced today are used in embedded systems, and recently the number of embedded systems in use has become larger than the number of humans on the planet.

The Travelling Salesman Problem is a classic problem of Combinatorial Optimisation and involves routing around a number of cities in order to cover the minimum total distance. It is notoriously difficult to solve practical sized instances optimally. The classical Integer Programming formulation involves an exponential number of constraints.

Many combinatorial (optimisation) problems have natural models based on, or including, set variables and set constraints. This was already known to the constraint programming community, and solvers based on constructive search for set variables have been around for a long time. In this paper, set variables and set constraints are put into a local-search framework, where concepts such as configurations, penalties, and neighbourhood functions are dealt with generically. This scheme is then used to define the penalty functions for five (global) set constraints, and to model and solve two well-known applications.

This paper introduces a problem called the temporal knapsack problem, presents several algorithms for solving it, and compares their performance. The temporal knapsack problem is a generalisation of the knapsack problem and specialisation of the multidimensional (or multiconstraint) knapsack problem. It arises naturally in applications such as allocating communication bandwidth or CPUs in a multiprocessor to bids for the resources. The algorithms considered use and combine techniques from constraint programming, artificial intelligence and operations research.

In face of the unwieldiness of non-monotonic logic engines, or Prolog/CLP meta interpreters as they are commonly used for model based reasoning and diagnosis, this paper proposes a simple, but effective improvement for performing the complex diagnostic task. The chosen approach is twofold: firstly, the problem of contradicting first order system descriptions with a set of observations is reduced to propositional logic using the notion of symptoms, and secondly, the determination of conflict sets and minimal diagnoses is mapped to a problem whose technical solution has experienced a sheer boost over the past years, namely -satisfiability using state-of-the-art SAT-solvers. Since the involved problems are (mostly) -complete, the ideas for additional improvements for a more diagnosis-specific SAT-solver are also sketched and their implementation by means of a non-destructive solver, LSAT, evaluated.

This article presents an arc-consistency algorithm for the constraint, which enforces the partitioning of a digraph = () into a set of vertex-disjoint anti-arborescences. It provides a necessary and sufficient condition for checking the constraint in time, as well as a complete filtering algorithm taking time.

The constraint counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing even the lower bound on the number of values is NP-hard. We therefore study different approximation heuristics for this problem. We introduce three new methods for computing a lower bound on the number of values. The first two are based on the and are incomparable to a previous approach based on intervals. The last method is a linear relaxation of the problem. This gives a tighter lower bound than all other methods, but at a greater asymptotic cost.

Recent work have exhibited specific structure among combinatorial problem instances that could be used to speed up search or to help users understand the dynamic and static intimate structure of the problem being solved. Several Operations Research approaches apply decomposition or relaxation strategies upon such a structure identified within a given problem. The next step is to design algorithms that adaptatively integrate that kind of information during search. We claim in this paper, inspired by previous work on impact-based search strategies for constraint programming, that using an explanation-based constraint solver may lead to collect invaluable information on the intimate dynamic and static structure of a problem instance. We define several impact graphs to be used to design generic search guiding techniques and to identify hidden structures of instances. Finally, we discuss how dedicated OR solving strategies (such as Benders decomposition) could be adapted to constraint programming when specific relationships between variables are exhibited.

This paper presents a hybrid algorithm for a class of resource constrained scheduling problems based on decomposition. The general minimum completion time problem is considered, which has not been solved in a decomposed way by existing methods. The problem is first decomposed into an assignment master problem and a number of scheduling subproblems. The subproblem is formulated as both a constraint programming model and an integer programming model. The hybrid algorithm then combines constraint programming, integer programming and linear programming solvers in its three steps: the master problem solving, the subproblems solving and the cut generation. In particular, the cut generation method is based on the integer programming model, and in practice it is done by solving a linear program. Computational experiments have been carried out for the considered minimum completion time problems. The results show that the proposed algorithm could substantially reduce the solving time, compared with directly solving by mixed integer solvers.