Search

International audience; Local Search metaheuristics are a recognized means of solving hard combinatorialproblems. Over the last couple of decades, significant advances have beenmade in terms of the formalization, applicability and performance of these methods.Key to the performance aspect is the increased availability of parallel hardware,which turns out to be largely exploitable by this class of procedures. As thereal-life cases of combinatorial optimisation easily degrade into intractable territoryfor exact or approximation algorithms, local search metaheuristics hold undeniableinterest. This situation is further compounded by the good adequacy exhibited bythis class of search procedures for large-scale parallel operation. In this chapter weexplore and discuss ways which lead to parallelization in Local Search.

International audience; The Quadratic Assignment Problem is at the core of several real-life applications. Finding an optimal assignment is computationally very difficult, for many useful instances. The best results are obtained with hybrid heuristics, which result in complex solvers. We propose an alternate solution where hybridization is obtain by means of parallelism and cooperation between simple single-heuristic solvers. We present experimental evidence that this approach is very efficient and can effectively solve a wide variety of hard problems, often surpassing state-of-the-art systems.

International audience; Several real-life applications can be stated in terms of the Quadratic Assignment Problem. Finding an optimal assignment is com-putationally very difficult, for many useful instances. We address this problem using a local search technique, based on Extremal Optimization and present experimental evidence that this approach is competitive. Moreover, cooperative parallel versions of our solver improve performance so much that large and hard instances can be solved quickly.

International audience; We present the parallel implementation of a constraint-based Local Search algorithm and investigate its performance on several hardware plat-forms with several hundreds or thousands of cores. We chose as the basis for these experiments the Adaptive Search method, an efficient sequential Local Search method for Constraint Satisfaction Problems (CSP). After preliminary experiments on some CSPLib benchmarks, we detail the modeling and solving of a hard combinatorial problem related to radar and sonar applications: the Costas Array Problem. Performance evaluation on some classical CSP bench-marks shows that speedups are very good for a few tens of cores, and good up to a few hundreds of cores. However for a hard combinatorial search problem such as the Costas Array Problem, performance evaluation of the sequential version shows results outperforming previous Local Search implementations, while the parallel version shows nearly linear speedups up to 8,192 cores. The proposed parallel scheme is simple and based on independent multi-walks with no communication between processes during search. We also investigated a cooperative multi-walk scheme where processes share simple information, but this scheme does not seem to improve performance.

Constraint Programming is one approach to declarative programming where a problem is modeled as a set of variables with a domain and a set of relations constraints between them. Constraint-based Local Search builds on the idea of using constraints to describe and control local search. Problems are modeled using constraints and heuristics for which solutions are searched, using Local Search. With the progressing move toward multi and many-core systems, parallelism has become mainstream as the number of cores continues to increase. Declarative programming approaches such as those based on constraints need to be better understood and experimented in order to understand their parallel behaviour. In this paper, we discuss experiments we have been carrying out with Adaptive Search and present a new parallel version of it based on GPI, a recent API and programming model for the development of scalable parallel applications. Our experiments on different problems show interesting speed-ups and, more importantly, a better understanding of how these gains are obtained, in the context of declarative programming.

The Costas Array Problem is a highly combina- torial problem linked to radar applications. We present in this paper its detailed modeling and solving by Adaptive Search, a constraint-based local search method. Experiments have been done on both sequential and parallel hardware up to several hundreds of cores. Performance evaluation of the sequential version shows results outperforming previous implementations, while the parallel version shows nearly linear speedups up to 8,192 cores.

International audience; We explore the use of the Cell Broadband Engine (Cell/BE for short) for combinatorial optimization applications: we present a parallel version of a constraint-based local search algorithm that has been implemented on a multiprocessor BladeCenter machine with twin Cell/BE processors (total of 16 SPUs per blade). This algorithm was chosen because it fits very well the Cell/BE architecture and requires neither shared memory nor communication between processors, while retaining a compact memory footprint. We study the performance on several large optimization benchmarks and show that this achieves mostly linear time speedups, even sometimes super-linear. This is possible because the parallel implementation might explore simultaneously different parts of the search space and therefore converge faster towards the best sub-space and thus towards a solution. Besides getting speedups, the resulting times exhibit a much smaller variance, which benefits applications where a timely reply is critical.

International audience; The current proposals for the inclusion of modules in the ISO Prolog standard are not very consensual. Since a program-structuring feature is required for a production programming language, several alternatives have been explored over the years. In this article we recall and expand on the concepts of Contextual Logic Programming, a powerful and simple mechanism which addresses the general issue of modularity in Logic Programs. We claim that unit arguments are an essential addition to this programming model, illustrate the claim with examples and draw parallels with Object-Oriented programming. We argue that Contextual Logic Programming is an interesting and effective tool for the development of large-scale programs built upon the Contextual Logic Programming paradigm and argue that contexts with arguments actually provide a powerful, expressive and very convenient means of structuring large applications upon a Prolog basis. We substantiate our claims with examples taken mostly from a "real world" application, Universidade de Evora's ' Academic Information System, which is currently being developed using the prototype implementation described in this article. We sketch the most relevant aspects of a new implementation of Contextual Logic Programming, GNU Prolog/CX, focusing on the impact on performance of the features which were added to a regular Prolog system, highlighting the low overhead which is incurred in case these extensions are not used