Search

IBM ILOG CP Optimizer (CPO) provides a scheduling language supported by a robust and efficient automatic search. This paper summes up the major language constructs and shed some lights on their propagations. Among the main constructs it introduces the notion of interval variable which enable reasoning on conditional time-intervals representing activities or tasks that may or may not be executed in the final schedule. In Constraint-Based Scheduling, those problems are usually handled by defining new global constraints over classical integer variables. This dual perspective facilitates an easy modeling process while ensuring a strong constraint propagation and an efficient search in the engine. The approach forms the foundations of the new generation of scheduling model and algorithms provided in CPO. Small examples are provided at the end of the language construct, however at the end of the paper three larger/real life examples recently studied in the scheduling literature are presented along some computational results illustrating both the expressivity of the modeling language and the robustness of the automatic search. Interestingly all three problems can easily be modeled with the language in only a few dozen lines (the complete models are provided) and on average the automatic search outperforms existing problem specific approaches.

In this article, we explore how neighborhoods for the Large Neighborhood Search (LNS) framework can be automatically defined by the volume of propagation of our Constraint Programming (CP) solver. Thus we can build non trivial neighborhoods which will not be reduced to zero by propagation and whose size will be close to a parameter of the search. Furthermore, by looking at the history of domain reductions, we are able to deduce even better neighborhoods. This idea is validated by numerous experiments with the car sequencing problem. The result is a powerful and completely automatic method that is able to beat our hand-written neighborhoods both in term of performance and of stability. This is in fact the first time for us that a completely generic code is better than a hand-written one.

Car sequencing is a well-known difficult problem. It has resisted and still resists the best techniques launched against it. Instead of creating a sophisticated search technique specifically designed and tuned for this problem, we will combine different simple local search-like methods using a portfolio of algorithms framework. In practice, we will base our solver on a powerful LNS algorithm and we will use the other local search-like algorithms as a diversification schema for it. The result is an algorithm is competitive with the best known approaches.

We introduce a constraint for one-dimensional bin packing. This constraint uses propagation rules incorporating knapsack-based reasoning, as well as a lower bound on the number of bins needed. We show that this constraint can significantly reduce search on bin packing problems. We also demonstrate that when coupled with a standard bin packing search strategy, our constraint can be a competitive alternative to established operations research bin packing algorithms.

Industrial optimization applications must be "robust," i.e., must provide good solutions to problem instances of different size and numerical characteristics, and continue to work well when side constraints are added. This paper presents a case study in which this requirement and its consequences on the applicability of different optimization techniques have been addressed. An extensive benchmark suite, built on real network design data provided by France Telecom R&D, has been used to test multiple algorithms for robustness against variations in problem size, numerical characteristics, and side constraints. The experimental results illustrate the performance discrepancies that have occurred and how some have been corrected. In the end, the results suggest that we shall remain very humble when assessing the adequacy of a given algorithm for a given problem, and that a new generation of public optimization benchmark suites is needed for the academic community to attack the issue of algorithm robustness as it is encountered in industrial settings.

We use a local search method we term Large Neighbourhood Search (LNS) to solve vehicle routing problems. LNS is analogous to the shuffling technique of job-shop scheduling, and so meshes well with constraint programming technology. LNS explores a large neighbourhood of the current solution by selecting a number of "related" customer visits to remove from the set of planned routes, and re-inserting these visits using a constraint-based tree search. Unlike similar methods, we use Limited Discrepancy Search during the tree search to re-insert visits. We analyse the performance of our method on benchmark problems. We demonstrate that results produced are competitive with Operations Research meta-heuristic methods, indicating that constraint-based technology is directly applicable to vehicle routing problems.

A boundary integral equation formulation is developed for a Poisson equation with a linearly layered conductivity, using 2D and 3D Green’s functions obtained for this heterogeneous medium problem found a corresponding 3D and 4D axisymmetric Green’s function for a homogeneous material.

The SPACE machine is introduced as a new type of computer architecture, capable of very fast simulation of highly concurrent systems. The machine is designed to be scalable, constructed from a vast array of boards. The decisions made in the the design of the board are discussed, and the actual hardware (based on an array of Field Programmable Gate Array chips) is described. It is shown that this machine can be programmed by translating a subset of the Occam language into asynchronous modules. Using the Circal process algebra, a new method of formally verifying asynchronous modules for these circuits is presented. This method allows bounded gate delays to be included in a two-level modelling mechanism.