Catálogo de publicaciones - libros

As backtracking search explores paths in its search tree it makes various inferences about the problem. The inferences search computes can be very computationally expensive to compute statically. However, in most backtracking CSP solvers this information is discarded when the search backtracks along the current path.

This talk consists of two interwoven stories. The Happy Story presents a technical solution to the problem of optimizing for cost instead of the more normal metric of duration. We describe a mechanism whereby the optimization problem is split into an evaluation component, where the projected cost of a schedule is evaluated using dynamic programming techniques, and a search component, where search is conducted in “window space” to find a cost-efficient schedule.

Most of the currently active Earth-observing satellites are entirely controlled from the ground: observation plans are regularly computed on the ground (typically each day for the next day), uploaded to the satellite using visibility windows, and then executed onboard as they stand. Because the possible presence of clouds is the main obstacle to optical observation, meteorological forecasts are taken into account when building these observation plans. However, this does not prevent most of the performed observations to be fruitless because of the unforeseen presence of clouds. To fix this problem, the possibility of equipping Earth-observing satellites with an extra instrument dedicated to the detection of the clouds in front of it, just before observation, is currently considered. But, in such conditions, decision upon the observations to be performed can be no longer made offline on the ground. It must be performed online onboard, because it must be performed at the last minute when detection information is available and because visibility windows between Earth-observing satellites and their control centers are short and rare. With agile Earth-observing satellites which are the next generation ones, decision-making upon observation requires the computing of an as short as possible attitude trajectory allowing the satellite to point to the right ground area within its visibility window. In this paper, we show the results of an experiment consisting in using a continuous constraint satisfaction problem solver (RealPaver) to compute such optimal trajectories online onboard.

In this paper, the embodiment design of an air conditioning system (ACS) in an aircraft is investigated using interval constraint satisfaction techniques. The detailed ACS model is quite complex to solve, since it contains many coupled variables and many constraints corresponding to complex physics phenomena. Some new heuristics and notions based on embodiment design knowledge, are briefly introduced to undertake some embodiment design concepts and to obtain a more relevant and more efficient solving process than classical algorithms.

The benefits of using constraint programming in embodiment design are discussed and some difficulties for designers using CP tools are shortly detailed.

Salinity is the relative concentration of salts in water. In a city of southern China, the local water supply company pumps water from a nearby river for potable use. During the winter dry season, the intrusion of sea water raises the salinity of the river to a high level and affects approximately the daily life of 450,000 residents of the city. This paper reports the application of constraint programming (CP) to optimize the logistical operations of the raw water system so as to satisfy the daily water consumption requirement of the city and to keep the potable salinity below a desirable level for as many days as possible. CP is the key to the success of the project for its separation of concerns and powerful constraint language that allows for rapid construction of a functional prototype and production system. Flexibility and adaptiveness allow us to deal with our clients’ many changes in the requirements. Deriving good variable and value ordering heuristics, and generating useful implied constraints, we demonstrate that branch-and-bound search with constraint propagation can cope with an optimization problem of large size and great difficulty.

Recently, constraint-programming techniques have been used to generate test data and to verify the conformity of a program with its specification. Constraint generated for these tasks may involve integer ranging on all machine-integers, thus, the constraint-based modeling of the program and its specification is a critical issue. In this paper we investigate different models. We show that a straightforward translation of a program and its specification in a system of guarded constraints is ineffective. We outline the key role of Boolean abstractions and explore different search strategies on standard benchmarks.

We present an overview of a system developed by IBM for generating short-term operations schedules for a large steel manufacturer. The problem addressed by the system was challenging due to the combination of detailed resource allocation and scheduling constraints and preferences, sequence dependent setup times, tight minimum and maximum inventory level constraints between processes, and constraints on the minimum and maximum levels of production by shift for each product group. We have developed a domain-specific decomposition based approach that uses mixed-integer programming to generate a high-level plan for production, and constraint programming to generate a schedule at fine level of time granularity taking into account detailed scheduling constraints and preferences. In this paper we give an overview of the problem domain and solution approach, and present a detailed description of the constraint programming part of the system. We also discuss the impact the system is having with the customer on their manufacturing operations.

The steel mill slab design problem from the CSPLIB is real-life problem from the steel industry. Finding optimal solutions to this problem is difficult. Existing constraint programming approaches can solve problems up to 30 orders. We propose a strong constraint programming model based on logical and global constraints. By designing a specific strategy for variable and value selection, we are able to solve instances having more than 70 orders to optimality using depth-first search. Injecting this strategy into a large neighborhood search, we are able to solve the real-life instance of the CSPLIB having 111 orders in just 3 seconds.

LODE is a logic-based web tool for Italian deaf children. It aims at stimulating global reasoning on e-stories written in a verbal language. Presently, we are focusing on temporal reasoning, that is, LODE stimulates children to reason with global temporal relations between events possibly distant in a story. This is done through apt exercises and with the support of a constraint programming system. Children can also reinvent the e-story by rearranging its events along a new temporal order; it is the task of the constraint system to determine the consistency of the temporally reorganised story and provide children with feedback. To the best of our knowledge, LODE is the first e-learning tool for Italian deaf children that aims at stimulating global reasoning on whole e-stories.

Alcatel-Lucent is a major player in the field of telecommunications. One of the products it offers to network operators is wireless infrastructure such as base stations. Such equipment is delivered in cabinets. These cabinets are packed with various pieces of electronics: filters, amplifiers, circuit packs, etc. The exact configuration of a cabinet is dependent upon the circumstances it is being placed in, and some 20 product groups can be distinguished. However, the variation in cabinets is large, even within one product group. For this reason, they are built to order.

In order to improve cost, yield and delivery performance, lean manufacturing concepts were applied to change the layout of the factory to one based on . These cells focus on improving manufacturing through standardised work, limited changeovers between product groups and better utilisation of test equipment. A key component in the implementation of these improvements is a system which schedules the cells to satisfy customer request dates in an efficient sequence.

This paper describes the transformation and the tool that was built to support the new method of operations. The implementation has achieved significant improvements in manufacturing interval, work in process inventory, first test yield, headcount, quality (i.e. fewer defects are found during the testing stage) and delivery performance. Although these benefits are mainly achieved because of the change to a cell layout, the scheduling tool is crucial in realising the full potential of it.