Results 1-2 of 2.
malika mehdi

Bookmark and Share    
Full Text
Peer Reviewed
See detailSolving the three dimensional quadratic assignment problem on a computational grid
Mezmaz, Mohand; Mehdi, Malika UL; Bouvry, Pascal UL et al

in Cluster Computing (2014), 17(2), 205-217

The exact resolution of large instances of combinatorial optimization problems, such as three dimensional quadratic assignment problem (Q3AP), is a real challenge for grid computing. Indeed, it is ... [more ▼]

The exact resolution of large instances of combinatorial optimization problems, such as three dimensional quadratic assignment problem (Q3AP), is a real challenge for grid computing. Indeed, it is necessary to reconsider the resolution algorithms and take into account the characteristics of such environments, especially large scale and dynamic availability of resources, and their multi-domain administration. In this paper, we revisit the design and implementation of the branch and bound algorithm for solving large combinatorial optimization problems such as Q3AP on the computational grids. Such gridification is based on new ways to effi- ciently deal with some crucial issues, mainly dynamic adaptive load balancing and fault tolerance. Our new approach allowed the exact resolution on a nation-wide grid of a dif- ficult Q3AP instance. To solve this instance, an average of 1,123 computing cores were used for less than 12 days with a peak of around 3,427 computing cores. [less ▲]

Detailed reference viewed: 13 (0 UL)
Full Text
See detailParallel hybrid optimization methods for permutation based problems
Mehdi, Malika UL

Doctoral thesis (2011)

Solving efficiently large benchmarks of NP-hard permutation-based problems requires the development of hybrid methods combining different classes of optimization algorithms. The key challenge here is how ... [more ▼]

Solving efficiently large benchmarks of NP-hard permutation-based problems requires the development of hybrid methods combining different classes of optimization algorithms. The key challenge here is how to find connections between the divergent search strategies used in each class of methods in order to build efficient hybridization strategies. Genetic algorithms (GAs) are very popular population-based metaheuristics based on stochastic evolutionary operators. The hybridization of GAs with tree-based exact methods such as Branch-and-Bound is a promising research trend. B&B algorithms are based on an implicit enumeration of the solution space represented as a tree. Our hybridization approach consists in providing a common solution and search space coding and associated search operators enabling an efficient cooperation between the two methods. The tree-based representation of the solution space is traditionally used in B&B algorithms to enumerate the solutions of the problem at hand. In this thesis, this special representation is adapted to metaheuristics. The encoding of permutations as natural numbers, which refer to their lexicographic enumeration in the tree, is proposed as a new way to represent the solution space of permutation problems in metaheuristics. Mapping functions between the two representations and special search operators are defined for general permutation problems. This common representation allows the design of efficient cooperation strategies between GAs and B&B algorithms. The proposed hybrid schemes have been parallelized and validated on standard benchmarks of the 3D quadratic assignment problem (Q3AP) using the computational grid Grid5000. [less ▲]

Detailed reference viewed: 32 (9 UL)