Qubit allocation is a central step in adapting abstract quantum circuits to noisy intermediate-scale quantum devices, yet exact approaches for solving it face severe scalability limitations. In this work, we revisit the formulation of qubit allocation as a permutation-based quadratic assignment problem and develop a branch-and-bound algorithm for its exact resolution. We first establish a refined sequential implementation that achieves significantly faster runtimes than previous exact approaches on most problem instances, thereby setting a new state-of-the-art for this formulation. Building on this foundation, we extend the approach to a performance-aware parallel implementation that exploits both intra-node and inter-node parallelism on High-Performance Computing (HPC) infrastructures. Our experimental evaluation demonstrates near-linear strong scaling at the intra-node level and substantial scalability in distributed settings across nodes. Leveraging these capabilities, we provide reference optimal solutions for challenging benchmark circuits of up to 26 qubits—significantly larger than previously reported instances. These results show that large-scale parallelization can effectively extend the reach of exact methods for qubit allocation, thereby advancing the integration of combinatorial optimization and HPC techniques in quantum computing.

In this paper, we investigate the application of Genetic Algorithms (GAs) and their parallelization via the Island Model (IMGA) for polygonal image reconstruction. The objective is to approximate a target image using a fixed number of colored triangles, formulating the problem as a high-dimensional optimization challenge. A standard GA is first implemented to assess its effectiveness using various objective functions. We then introduce a parallel IMGA framework, featuring multiple subpopulations evolving independently with periodic migration in a ring topology. Migration parameters are calibrated, revealing optimal settings for preserving diversity and improving convergence. Experimental results indicate that IMGA achieves up to a 50% improvement in reconstruction quality compared to the standard GA, with minimal additional computational cost. Moreover, our approach significantly outperforms the current state of the art for this problem, which relies on a hybrid method combining genetic algorithms and machine learning. These findings highlight the effectiveness and scalability of island models in addressing complex, high-dimensional optimization problems such as image reconstruction.

ABSTRACT The Branch‐and‐Bound (B&B) technique plays a key role in solving many combinatorial optimization problems, enabling efficient problem‐solving and decision‐making in a wide range of applications. It incrementally constructs a tree by building candidates to the solutions and abandoning a candidate as soon as it determines that it cannot lead to an optimal solution. With modern problems growing increasingly large, accelerating B&B algorithms through parallelization has become a critical challenge for handling large solution spaces. At the same time, modern parallel computing systems themselves are becoming larger, more heterogeneous, and more diverse, requiring programming approaches capable of effectively exploiting such complexity. To address these challenges, this work presents a GPU‐accelerated B&B algorithm based on the Partitioned Global Address Space (PGAS) programming model, implemented using the Chapel language. The PGAS‐based design is motivated by the high‐level abstraction provided by this programming model, which favors programmability, whereas vendor‐neutral GPU features of the Chapel language favor GPU portability. The algorithm uses a pool‐based approach for generality and exploits a dynamic load balancing mechanism for performance scalability. Extensive experimentation on the N‐Queens and permutation flowshop scheduling problems demonstrated both code performance and code portability of the proposed algorithm on several GPU architectures compared to optimized CUDA‐based implementations. Moreover, the strong scaling efficiency of the proposed algorithm is investigated on a TOP500 pre‐exascale supercomputer up to 1024 GPUs.

Abstract With the recent arrival of the exascale era, modern supercomputers are increasingly big making their programming much more complex. In addition to performance, software productivity is a major concern to choose a programming language, such as Chapel, designed for exascale computing. In this paper, we investigate the design of a parallel distributed tree‐search algorithm, namely P3D‐DFS, and its implementation using Chapel. The design is based on the Chapel's DistBag data structure, revisited by: (1) redefining the data structure for Depth‐First tree‐Search (DFS), henceforth renamed DistBag‐DFS; (2) redesigning the underlying load balancing mechanism. In addition, we propose two instantiations of P3D‐DFS considering the Branch‐and‐Bound (B&B) and Unbalanced Tree Search (UTS) algorithms. In order to evaluate how much performance is traded for productivity, we compare the Chapel‐based implementations of B&B and UTS to their best‐known counterparts based on traditional OpenMP (intra‐node) and MPI+X (inter‐node). For experimental validation using 4096 processing cores, we consider the permutation flow‐shop scheduling problem for B&B and synthetic literature benchmarks for UTS. The reported results show that P3D‐DFS competes with its OpenMP baselines for coarser‐grained shared‐memory scenarios, and with its MPI+X counterparts for distributed‐memory settings, considering both performance and productivity‐awareness. In the context of this work, this makes Chapel an alternative to OpenMP/MPI+X for exascale programming.

Inspired by the recent success of parallelized exact methods to solve difficult scheduling problems, we present preliminary results of a general parallel beam search framework for combinatorial optimization problems. Beam search is a constructive metaheuristic traversing a search tree layer by layer while keeping in each layer a bounded number of promising nodes to consider many partial solutions in parallel. We propose a variant which is suitable for intra-node parallelization by multithreading with data parallelism. For sufficiently large problem instances and beam widths our work-in-progress implementation in the JIT-compiled Julia language admits promising speed-ups over 30x on 32 cores with uniform memory access for the Permutation Flow Shop Scheduling (PFSP) problem with flowtime objective.

Efficient Global Optimization (EGO) is widely used for the optimization of computationally expensive black-box functions. It uses a surrogate modeling technique based on Gaussian Processes (Kriging). However, due to the use of a stationary covariance, Kriging is not well suited for approximating non stationary functions. This paper explores the integration of Deep Gaussian processes (DGP) in EGO framework to deal with the non-stationary issues and investigates the induced challenges and opportunities. Numerical experimentations are performed on analytical problems to highlight the different aspects of DGP and EGO.

Summary New GPGPU technologies, such as CUDA Dynamic Parallelism (CDP), can help dealing with recursive patterns of computation, such as divide‐and‐conquer, used by backtracking algorithms. In this paper, we propose a GPU‐accelerated backtracking algorithm using CDP that extends a well‐known parallel backtracking model. The search starts on CPU, processing the search tree until a first cutoff depth. Based on this partial backtracking tree, the algorithm analyzes the memory requirements of subsequent kernel generations. The proposed algorithm performs no dynamic allocation of memory on GPU, unlike related works from the literature. The proposed algorithm has been extensively tested using the N‐Queens Puzzle problem and instances of the Asymmetric Traveling Salesman Problem (ATSP) as test‐cases. The proposed CDP algorithm may, under some conditions, outperform its non‐CDP counterpart by a factor up to 25. But, it may also be up to twice slower. The CDP‐based implementation has much better worst case execution times and makes algorithm's performance less dependent on the tuning of parameters. Compared to other CDP‐based strategies from the literature, the proposed algorithm is on average 8× faster. The proposed algorithm is also hybridized with another CDP‐based strategy from the literature. The combination of strategies is in average 4.5× faster than the related strategy. We also identify some difficulties, limitations, and bottlenecks concerning the CDP programming model which may be useful for helping potential users.

Summary In this paper, we aim to propose a parallel multi‐core hyper‐heuristic based on greedy randomized adaptive search procedure (GRASP) for the permutation flow‐shop problem with the makespan criterion. The GRASP is a well‐known two‐phase metaheuristic. First, a construction phase builds a complete solution iteratively, component by component, by a greedy randomized algorithm. After that, a local search phase improves this solution. The choice of a component and the order in which it is added in a solution mostly depend on its incremental cost. Thus, a basic GRASP configuration is defined by a cost function, a probabilistic parameter of greediness and a neighbourhood structure. We consider five cost functions and seven well‐known neighbourhood structures. In this paper a cost function based on a bounding operator is integrated in GRASP for the first time. Mechanisms that investigate automatically algorithm configurations refer to hyper‐heuristics. Our hyper‐heuristic investigates 315 GRASP configurations and reports which one produces better results. Parallel multi‐core computing is used as a way to efficiently implement the hyper‐heuristic. Taillard's benchmark instances are used to test the hyper‐heuristic for the permutation flow‐shop problem. Copyright © 2016 John Wiley & Sons, Ltd.

Summary Tree‐based exploratory methods, like Branch‐and‐Bound (B&B) algorithms, are highly irregular applications which makes their design and implementation on graphics processing unit (GPU) challenging. In this paper, we present a multi‐GPU B&B algorithm for solving large permutation‐based combinatorial optimization problems. To tackle the problem of the irregular workload, we propose a hierarchical work stealing (WS) strategy that balances the workload inside the GPU and between different GPUs and CPU cores. Our B&B is based on an Integer‐Vector‐Matrix data structure instead of a pool of permutations, and work units exchanged are intervals of factoradics instead of sets of nodes. Two variants of the algorithm, using the same hierarchical WS strategy, are proposed: one for combinatorial optimization problems where the evaluation of nodes is costly and one for fine‐grained problems. The latter variant uses a new hypercube‐based WS strategy and a trigger mechanism to balance the work load inside the GPU. The proposed approach has been extensively experimented using the flowshop scheduling, the n‐queens and the asymmetric travelling salesman problems as test‐cases. The reported results show that the proposed hierarchical WS mechanism is capable of handling fine and coarse‐grained types of workloads efficiently, reaching near‐linear speed‐up on up to four GPUs for a set of ten flowshop instances and large instances of fine‐grained problems. Copyright © 2016 John Wiley & Sons, Ltd.

International audience

Summary In this paper, the focus is put on multi‐core branch‐and‐bound algorithms for solving large‐scale permutation‐based optimization problems. We investigate five work stealing (WS) strategies with a new data structure called integer–vector–matrix (IVM). In these strategies, each thread has a private IVM allowing the local management of a set of subproblems enumerated using a factorial system. The WS strategies differ in the way the victim thread is selected and the granularity of stolen work units (intervals of factoradics). To assess the efficiency of the private IVM‐based WS approach, the five WS strategies have been extensively experimented on the flowshop scheduling permutation problem and compared with their conventional linked‐list‐based counterparts. The obtained results demonstrate that the IVM‐based WS outperforms the linked‐list‐based one in terms of CPU time, memory usage and number of performed WS operations. Copyright © 2016 John Wiley & Sons, Ltd.

Many real-world problems in different industrial and economic fields are permutation combinatorial optimization problems. Solving to optimality large instances of these problems, such as flowshop problem, is a challenge for multi-core computing. This paper proposes a multi-threaded factoradic-based branch-and-bound algorithm to solve permutation combinatorial problems on multi-core processors. The factoradic, called also factorial number system, is a mixed radix numeral system adapted to numbering permutations. In this new parallel algorithm, the B&B is based on a matrix of integers instead of a pool of permutations, and work units exchanged between threads are intervals of factoradics instead of sets of nodes. Compared to a conventional pool-based approach, the obtained results on flowshop instances demonstrate that our new factoradic-based approach, on average, uses about 60 times less memory to store the pool of subproblems, generates about 1.3 times less page faults, waits about 7 times less time to synchronize the access to the pool, requires about 9 times less CPU time to manage this pool, and performs about 30,000 times less context switches.

SUMMARY Branch‐and‐bound (B&B) algorithms are attractive methods for solving to optimality combinatorial optimization problems using an implicit enumeration of a dynamically built tree‐based search space. Nevertheless, they are time‐consuming when dealing with large problem instances. Therefore, pruning tree nodes (subproblems) is traditionally used as a powerful mechanism to reduce the size of the explored search space. Pruning requires to perform the bounding operation, which consists of applying a lower bound function to the subproblems generated during the exploration process. Preliminary experiments performed on the Flow‐Shop scheduling problem (FSP) have shown that the bounding operation consumes over 98%of the execution time of the B&B algorithm. In this paper, we investigate the use of graphics processing unit (GPU) computing as a major complementary way to speed up the search. We revisit the design and implementation of the parallel bounding model on GPU accelerators. The proposed approach enables data access optimization. Extensive experiments have been carried out on well‐known FSP benchmarks using an Nvidia Tesla C2050 GPU card. Compared to a CPU‐based single core execution using an Intel Core i7‐970 processor without GPU, speedups higher than 100 times faster are achieved for large problem instances. At an equivalent peak performance, GPU‐accelerated B&B is twice faster than its multi‐core counterpart. Copyright © 2013 John Wiley & Sons, Ltd.

Solving to optimality large instances of combinatorial optimization problems using Brand and Bound (B&B) algorithms requires a huge amount of computing resources. In this paper, we investigate the design and implementation of such algorithms on computational grids. Most of existing grid-based B&B algorithms are based on the Master-Worker paradigm, their scalability is therefore limited. In addition, even if the volatility of resources is a major issue in grids fault tolerance is rarely addressed in these works. We thereby propose FTH-B&B, a fault tolerant hierarchical B&B. FTH-B&B is based on different new mechanisms enabling to efficiently build and maintain balanced the hierarchy, and to store and recover work units (sub-problems). FTH-B&B has been implemented on top of the ProActive grid middleware and programming environment and applied to the Flow-Shop scheduling problem. Very often, the validation of existing grid-based B&B works is performed either through simulation or a very small real grid. In this paper, we experimented FTH-B&B on the Grid’5000 real French nation-wide computational grid using up to 1,900 processor cores distributed over six sites. The reported results show that the overhead induced by the proposed mechanisms is very low and an efficiency close to 100 percent can be achieved on some Taillards benchmarks of the Flow-Shop problem. In addition, the results demonstrate the robustness of the proposed mechanisms even in extreme failure situations.

In this paper, we deal with cloud brokering for the assignment optimization of VM requests in three-tier cloud infrastructures. We investigate the Pareto-based meta-heuristic approach to take into account multiple client and broker-centric optimization criteria. We propose a new multi-objective Genetic Algorithm (MOGA-CB ) that can be integrated in a cloud broker. Two objectives are considered in the optimization process: minimizing both the response time and the cost of the selected VM instances to satisfy the clients and to maximize the profit of the broker. The approach has been experimented using realistic data of different types of Amazon EC2 instances and their pricing history. The reported results show that MOGA-CB provides efficiently effective Pareto sets of solutions.

Public cloud computing allows one to rent virtual servers on a hourly basis. This raises the problematic of being able to decide which server offers to take, which providers to use, and how to use them to acquire sufficient service capacity, while maintaining a cost effective platform. This article proposes a new realistic model to tackle the problem, placing services into IAAS virtual machines from multiple providers. A flexible protocol is defined to generate real-life instances, and applied on two industrial cases with four real cloud providers. An evolutionary approach, with new specific operators, is introduced and compared to a MIP formulation. Experiments conducted on two data-sets show that the evolutionary approach is viable to tackle real-size instances in reasonable amount of time.

In this paper, we propose a pioneering framework called ParadisEO-MO-GPU for the reusable design and implementation of parallel local search metaheuristics (S- Metaheuristics)on Graphics Processing Units (GPU). We revisit the ParadisEO-MO software framework to allow its utilization on GPU accelerators focusing on the parallel iteration-level model, the major parallel model for S- Metaheuristics. It consists in the parallel exploration of the neighborhood of a problem solution. The challenge is on the one hand to rethink the design and implementation of this model optimizing the data transfer between the CPU and the GPU. On the other hand, the objective is to make the GPU as transparent as possible for the user minimizing his or her involvement in its management. In this paper, we propose solutions to this challenge as an extension of the ParadisEO framework. The first release of the new GPU-based ParadisEO framework has been experimented on the permuted perceptron problem. The preliminary results are convincing, both in terms of flexibility and easiness of reuse at implementation, and in terms of efficiency at execution on GPU.

SUMMARY In this paper, we address the design and implementation of graphical processing unit (GPU)‐accelerated branch‐and‐bound algorithms (B&B) for solving flow‐shop scheduling optimization problems (FSP). Such applications are CPU‐time consuming and highly irregular. On the other hand, GPUs are massively multithreaded accelerators using the single instruction multiple data model at execution. A major issue that arises when executing on GPU, a B&B applied to FSP is thread or branch divergence. Such divergence is caused by the lower bound function of FSP that contains many irregular loops and conditional instructions. Our challenge is therefore to revisit the design and implementation of B&B applied to FSP dealing with thread divergence. Extensive experiments of the proposed approach have been carried out on well‐known FSP benchmarks using an Nvidia Tesla (C2050 GPU card ( http://www.nvidia.com/docs/IO/43395/NV_DS_Tesla_C2050_C2070_jul10_lores.pdf )). Compared with a CPU‐based execution, accelerations up to × 77.46 are achieved for large problem instances. Copyright © 2012 John Wiley & Sons, Ltd.

Local search metaheuristics (LSMs) are efficient methods for solving complex problems in science and industry. They allow significantly to reduce the size of the search space to be explored and the search time. Nevertheless, the resolution time remains prohibitive when dealing with large problem instances. Therefore, the use of GPU-based massively parallel computing is a major complementary way to speed up the search. However, GPU computing for LSMs is rarely investigated in the literature. In this paper, we introduce a new guideline for the design and implementation of effective LSMs on GPU. Very efficient approaches are proposed for CPU-GPU data transfer optimization, thread control, mapping of neighboring solutions to GPU threads, and memory management. These approaches have been experimented using four well-known combinatorial and continuous optimization problems and four GPU configurations. Compared to a CPU-based execution, accelerations up to \times 80 are reported for the large combinatorial problems and up to \times 240 for a continuous problem. Finally, extensive experiments demonstrate the strong potential of GPU-based LSMs compared to cluster or grid-based parallel architectures.

Branch-and-Bound (B&B) algorithms are time-intensive tree-based exploration methods for solving to optimality combinatorial optimization problems. In this paper, we investigate the use of GPU computing as a major complementary way to speed up those methods. The focus is put on the bounding mechanism of B&B algorithms, which is the most time consuming part of their exploration process. We propose a parallel B&B algorithm based on a GPU-accelerated bounding model. The proposed approach concentrate on optimizing data access management to further improve the performance of the bounding mechanism which uses large and intermediate data sets that do not completely fit in GPU memory. Extensive experiments of the contribution have been carried out on well-known FSP benchmarks using an Nvidia Tesla C2050 GPU card. We compared the obtained performances to a single and a multithreaded CPU-based execution. Accelerations up to X100 are achieved for large problem instances.

To deal with dynamic load balancing in large scale distributed systems, we propose to organize computing resources following a logical peer-to-peer overlay and to distribute the load according to the so-defined overlay. We use a tree as a logical structure connecting distributed nodes and we balance the load according to the size of induced sub trees. We conduct extensive experiments involving up to 1000 computing cores and provide a throughout analysis of different properties of our generic approach for two different applications, namely, the standard Unbalanced Tree Search and the more challenging parallel Branch-and-Bound algorithm. Substantial improvements are reported in comparison with the classical random work stealing and two finely tuned application specific strategies taken from the literature.

The quadratic 3-dimensional assignment problem (Q3AP) is an extension of the well-known NP-hard quadratic assignment problem. It has been proved to be one of the most difficult combinatorial optimization problems. Local search (LS) algorithms are a class of heuristics which have been successfully applied to solve such hard optimization problem. These methods handle with a single solution iteratively improved by exploring its neighborhood in the solution space. In this paper, we propose an iterated tabu search for solving the Q3AP. The design of this algorithm is essentially based on a new large neighborhood structure. Indeed, in LS heuristics, designing operators to explore large promising regions of the search space may improve the quality of the obtained solutions. However, designing such neighborhood is at the expense of a highly computationally process. Therefore, the use of graphics processing units (GPUs) provides an efficient complementary way to speed up the search. The proposed GPU-based iterated tabu search has been experimented on 5 different Q3AP instances. The obtained results are convincing both in terms of efficiency, quality and robustness of the provided solutions at run time.

Over the last years, interest in hybrid meta-heuristics has risen considerably in the field of optimization. Combinations of methods such as evolutionary algorithms and local searches have provided very powerful search algorithms. However, due to their complexity, the computational time of the solution search exploration remains exorbitant when large problem instances are to be solved. Therefore, the use of GPU-based parallel computing is required as a complementary way to speed up the search. This paper presents a new methodology to design and implement efficiently and effectively hybrid evolutionary algorithms on GPU accelerators. The methodology enables efficient mappings of the explored search space onto the GPU memory hierarchy. The experimental results show that the approach is very efficient especially for large problem instances.

When dealing with exponential search spaces and when no special knowledge is available on global optima, initial populations for population-based meta-heuristics should be uniformly distributed on the search space in order to sample basins of attraction of all local optima. In this paper, we propose a new initialization strategy for permutation problems. The new method is based on an original tree representation of the search space. Such representation was previously used for exact methods but never for meta-heuristics. The proposed method has been tested using a parallel Genetic Algorithm implemented in the ParadisEO framework and experimented on the Nationwide Grid5000 experimental grid using the Q3AP (3D QAP) permutation problem. The preliminary results are promising.

Precedence-constrained parallel applications are one of the most typical application model used in scientific and engineering fields. Almost all efforts, on this kind of applications, have focused on the minimization of makespan (completion time). It is only recently that much attention has been paid to energy consumption. In this paper, we address the precedence-constrained parallel applications on heterogeneous computing systems (HCSs). We propose a new bi-objective hybrid genetic algorithm that takes into account, not only makespan, but also energy consumption. This metaheuristic adopts dynamic voltage scaling (DVS) to minimize energy consumption. Our study provides promising results showing the significance and potential of DVS. The experimental results from our comparative evaluation study confirm the superior performance of our approach over the other known heuristics on the two criteria energy saving and completion time.

The island model for evolutionary algorithms allows to delay the global convergence of the evolution process and encourage diversity. However, solving large size and time-intensive combinatorial optimization problems with the island model requires a large amount of computational resources. GPU computing is recently revealed as a powerful way to harness these resources. In this paper, we focus on the parallel island model on GPU. We address its re-design, implementation, and associated issues related to the GPU execution context. The preliminary results demonstrate the effectiveness of the proposed approaches and their capabilities to fully exploit the GPU architecture.

Conformational sampling, the computational prediction of the experimental geometries of small proteins (folding) or of protein-ligand complexes (docking), is often cited as one of the most challenging multimodal optimization problems. Due to the extreme ruggedness of the energy landscape as a function of geometry, sampling heuristics must rely on an appropriate trade-off between global and local searching efforts. A previously reported ldquoplanetary strategyrdquo, a generalization of the classical island model used to deploy a hybrid genetic algorithm on computer grids, has shown a good ability to quickly discover low-energy geometries of small proteins and sugars, and sometimes even pinpoint their native structures-although not reproducibly. The procedure focused on broad exploration and used a tabu strategy to avoid revisiting the neighborhood of known solutions, at the risk of ldquoburyingrdquo important minima in overhastily set tabu areas. The strategy reported here, termed ldquodivide-and-conquer planetary modelrdquo couples this global search procedure to a local search tool. Grid nodes are now shared between global and local exploration tasks. The phase space is cut into ldquocellsrdquo corresponding to a specified sampling width for each of the N degrees of freedom. Global search locates cells containing low-energy geometries. Local searches pinpoint even deeper minima within a cell. Sampling width controls the important trade-off between the number of cells and the local search effort needed to reproducibly sample each cell. The probability to submit a cell to local search depends on the energy of the most stable geometry found within. Local searches are allotted limited resources and are not expected to converge. However, as long as they manage to discover some deeper local minima, the explored cell remains eligible for further local search, now relying on the improved energy level to enhance chances to be picked again. This competition prevents the system to waste too much effort in fruitless local searches. Eventually, after a limited number of local searches, a cell will be ldquoclosedrdquo and used - first as ldquoseedrdquo, later as tabu zone-to bias future global searches. Technical details and some folding and docking results will be discussed.

In the absence of a priori knowledge about global optima, initial populations in genetic algorithms (GAs) should at least be diversified, especially while dealing with large spaces. On the other hand, the use of parallel models for GAs helps to solve large instances. We will focus on the island model. In this paper we propose an island initialization technique for permutation-based problems. We exploit a virtual tree organisation commonly used in exact methods (Branch and Bound) to generate a fully disjoint and well distributed (over the search space) initial population in each island. This method can be used for all permutation-based problems (QAP, Flow-shop, Q3AP..). regardless of the number of permutations. Experiments are performed over Q3AP benchmarks using a $10$ island model. The results shows the efficiency of the proposed method especially for large instances.

In this paper we propose a parallel hybrid genetic method for solving Quadratic 3-dimensional Assignment Problem (Q3AP). This problem is proved to be computationally NP-hard. The parallelism in our algorithm is of two hierarchical levels. The first level is an insular model where a number of GAs (genetic algorithms) evolve in parallel. The second level is a parallel transformation of individuals in each GA. Implementation has been done using ParadisEO1 framework, and the experiments have been performed on GRID5000, the French nation-wide computational grid. To evaluate our method, we used three benchmarks derived from QAP instances of QAPLIB and the results are compared with those reported in the literature. The preliminary results show that the method is promising. The obtained solutions are close to the optimal values and the execution is efficient.

The branch and bound (B&B) algorithm is one of the most used methods to solve in an exact way combinatorial optimization problems. In a previous article, we proposed a new approach of the parallel B&B algorithm for distributed systems using the farmer-worker paradigm. However, the new farmer-worker approach has a disadvantage: some nodes of the B&B tree can be explored by several B&B processes. To prevent this redundant work and speed up, we propose a new P2P approach inspired from the strategies of existing P2P systems like Napster and JXTA. Validation is performed by experimenting the two approaches on mono-objective flow-shop problem instances using 500 processors belonging to the French national grid, Grid'5000. The obtained results prove the efficiency of the proposed P2P approach. Indeed, the execution time obtained with the P2P version, even if more communicative, is better than the farmer-worker's one.

Common evolutionary approaches to protein-ligand docking optimization use mutation operators based on Gaussian and Cauchy distributions, with local search hybrids. The choice of a local search method is important for an efficient algorithm. We investigate the impact of local search with mutation operators by performing a locality analysis. High locality means that small variations in the genotype imply small variations in the phenotype. Results show that local search hybrids reduce locality and act as local optimizers with the solution as a starting point.

Solving exactly Combinatorial Optimization Problems (COPs) using a Branch-and-Bound algorithm requires a huge amount of computational resources. The efficiency of such algorithm can be improved by distributing at large scale the computation required by the exploration of the search tree. In this paper, we propose ParallelBB, which is a P2P-based parallelization of the Branch-and-Bound algorithm for the computational Grid. The algorithm has been implemented using the ProActive distributed object Grid middleware. The algorithm has been applied to a mono- criterion permutation flow-shop problem and promisingly experimented on the Grid5000 computational Grid.

Computational simulations of conformational sampling in general, and of macromolecular folding in particular represent one of the most important and yet one of the most challenging applications of computer science in biology and medicinal chemistry. The advent of GRID computing may trigger some major progress in this field. This paper presents our first attempts to design GRID-based conformational sampling strategies, exploring the extremely rugged energy response surface in function of molecular geometry, in search of low energy zones through phase spaces of hundreds of degrees of freedom. We have generalized the classical island model deployment of genetic algorithms (GA) to a "planetary" model where each node of the grid is assimilated to a "planet" harboring quasi-independent multi-island simulations based on a hybrid GA-driven sampling approach. Although different "planets" do not communicate to each other-thus minimizing inter-CPU exchanges on the GRID-each new simulation will benefit from the preliminary knowledge extracted from the centralized pool of already visited geometries, located on the dispatcher machine, and which is disseminated to any new "planet". This "panspermic" strategy allows new simulations to be conducted such as to either be attracted towards an apparently promising phase space zone (biasing strategies, intensification procedures) or to avoid already in-depth sampled (tabu) areas. Successful folding of mini-proteins typically used in benchmarks for all- atoms protein simulations has been observed, although the reproducibility of these highly stochastic simulations in huge problem spaces is still in need of improvement. Work on two structured peptides (the "tryptophane cage" 1L2Y and the "tryptophane zipper" 1LE1) used as benchmarks for all-atom protein folding simulations has shown that the planetary model is able to reproducibly sample conformers from the neighborhood of the native geometries. However, within these neighborhoods (within ensembles of conformers similar to models published on hand of experimental geometry determinations), the energy landscapes are still extremely rugged. Therefore, simulations in general produce "correct" geometries (similar enough to experimental model for any practical purposes) which sometimes unfortunately correspond to relatively high energy levels and therefore are less stable than the most stable among misfolded conformers. The method thus reproducibly visits the native phase space zone, but fails to reproducibly hit the bottom of its rugged energy well. Intensifications of local sampling may in principle solve this problematic behavior, but is limited by computational resources. The quest for the optimal time point at which a phase space zone should stop being intensively searched and declared tabu, a very difficult problem, is still awaiting for a practically useful solution.

Real or academic combinatorial optimization problems are in the majority NP-hard. For large dimensions, an exact resolution is often impractical due to a limited amount of resources. The use of large scale deployment on distributed systems such as peer-to-peer (P2P) systems, based on exploiting free CPU cycles, provides an efficient way to reach high computing performance by distributing the computation to solve these problems. In this paper, we are interested in solving exactly optimization problems using parallel branch-and-bound algorithm on large scale distributed systems. We propose ParallelBB, which is a parallelization of the branch-and-bound algorithm and apply it to a mono-criterion permutation flow-shop problem. Furthermore, we develop P2PBB, which is the peer-to-peer implementation of our algorithm using ProActive

Solving optimally large instances of combinatorial optimization problems requires a huge amount of computational resources. In this paper, we propose an adaptation of the parallel branch and bound algorithm for computational grids. Such gridification is based on new ways to efficiently deal with some crucial issues, mainly dynamic adaptive load balancing, fault tolerance, global information sharing and termination detection of the algorithm. A new efficient coding of the work units (search sub-trees) distributed during the exploration of the search tree is proposed to optimize the involved communications. The algorithm has been implemented following a large scale idle time stealing paradigm (Farmer-Worker). It has been experimented on a flow-shop problem instance (Ta056) that has never been optimally solved. The new algorithm allowed to realize a success story as the optimal solution has been found with proof of optimality, within 25 days using about 1900 processors belonging to 9 Nation-wide distinct clusters (administration domains). During the resolution, the worker processors were exploited with an average of 97% while the farmer processor was exploited only 1.7% of the time. These two rates are good indicators on the efficiency of the proposed approach and its scalability.

A comparative study of parallel metaheuristics executed in grid environments is proposed, having as case study a genetic algorithm, a simulated annealing algorithm and a random search method. The random search method was constructed in order to offer a lower bound for the comparison. Furthermore, a conjugated gradient local search method is employed for each of the algorithms, at different points on the execution path. The algorithms are evaluated using the protein structure prediction problem, the benchmark instances consisting of the tryptophan-cage protein (Brookhaven protein data bank ID 1L2Y) and alpha-cyclodextrin. The algorithms are designed to benefit from the grid environment although having no particular optimization for the specified benchmarks. The presented results are obtained by running the algorithms independently and, in a second time, in conjunction with the conjugated gradient search method. Experimentations were performed on a nation-wide grid reuniting five distinct administrative domains and cumulating 400 CPUs. The complexity of the protein structure prediction problem remains prohibitive as far as large proteins are concerned, making the use of parallel computing on the computational grid essential for its efficient resolution.

The branch and bound (B&B) algorithm is one of the most used methods to solve in an exact way combinatorial optimization problems. This article focuses on the multi-objective version of this algorithm, and proposes a new parallel approach adapted to grid computing systems. This approach addresses several issues related to the characteristics of the algorithm itself and the properties of grid computing systems. Validation is performed by experimenting the approach on a bi-objective flow-shop problem instance that has never been solved exactly. Solving this instance, after several days of computation on a grid of more than 1000 processors, belonging to 7 distinct clusters, the obtained results prove the efficiency of the proposed approach

The focus of this paper is on the parallel multi-start and island models of meta-heuristics within the context of multiobjective optimization on the computational grid. The combination of these two models often provides very effective parallel algorithms. However, experiments on large-size problem instances are often stopped before the convergence of these algorithms is achieved. The full exploitation of the cooperation needs a large amount of computational resources and the management of the fault tolerance issue. In this paper, we propose a grid-based fault-tolerant approach for these models and their implementation on the XtremWeb grid middleware. The approach has been experimented on the bi-objective Flow-Shop problem on a computational grid which is a multi-domain education network composed of 321 heterogeneous Linux PCs. The preliminary results, obtained after an execution time of several days, demonstrate that the use of grid computing allows to fully exploit effectively and efficiently the two parallel models and their combination for solving challenging optimization problems. An improvement of the effectiveness by over 60% compared to a serial meta-heuristic is obtained with a computational grid.

This paper presents a parallel hybrid exact multi-objective approach which combines two metaheuristics - a genetic algorithm (GA) and a memetic algorithm (MA), with an exact method - a branch and bound (B&B) algorithm. Such approach profits from both the exploration power of the GA, the intensification capability of the MA and the ability of the B&B to provide optimal solutions with proof of optimality. To fully exploit the resources of a computational grid, the hybrid method is parallelized according to three well-known parallel models - the island model for the GA, the multi-start model for the MA and the parallel tree exploration model for the B&B. The obtained method has been experimented and validated on a bi-objective flow-shop scheduling problem. The approach allowed to solve exactly for the first time an instance of the problem - 50 jobs on 5 machines. More than 400 processors belonging to 4 administrative domains have contributed to the resolution process during more than 6 days

In this paper, we present ParadisEO-CMW, an extension of the open source ParadisEO framework, originally intended to the design and deployment of parallel hybrid meta heuristics on dedicated clusters of SMPs. Coupled with the Condor-MW library, it enables the execution of such parallel applications on volatile heterogeneous computational resources. The motivations, architecture and main features will be discussed. The framework has been tested by tackling a real-world NP-hard problem: feature selection in near-infrared spectroscopic data mining. It has been resolved by deploying a multi-level parallel model of evolutionary algorithms. Experimentations have been carried out on more than one hundred PCs originally intended for education. The obtained results are convincing, both in terms of flexibility and easiness at implementation, and in terms of efficiency and quality of provided solutions at execution.

This paper presents briefly the aims and challenges addressed in the GGM (Grid for Geno-Medicine) project. The idea behind the project is to offer a software infrastructure able to analyze and discover links between distributed medical and genetic data.

In this paper, we propose a formal model and a platform for software change management. The model is based on graphs rewriting, and deals with both multi-language source codes and heterogeneous database schemas. These are represented by software components linked by meaningful relationships. The change impact analysis is done, using a knowledge-based system, that includes impact propagation rules preserving the software consistency. This is implemented by an integrated platform including a multilanguage parsing tool, and a soft-ware change management module.

Rule mining consists of discovering valid and useful rules in large databases. As other data mining tasks, it is known to be time-consuming and I/O intensive. Evolutionary algorithms and parallelism are two important ways to deal with that performance problem. In this paper, we propose a parallel genetic algorithm for rule discovery, namely . We evaluated it on the Nursery School public domain data set available from the UCI Repository of Machine Learning databases. The results show that is efficient and allows to discover high quality rules.