Contributed Session Wed.2.H 3012

Wednesday, 13:15 - 14:45 h, Room: H 3012

Cluster 2: Combinatorial optimization [...]

Heuristics II


Chair: Abderrezak Mohamed Djadoun



Wednesday, 13:15 - 13:40 h, Room: H 3012, Talk 1

Salim Bouamama
A population-based iterated greedy algorithm for the minimum weight vertex cover problem

Coauthors: Christian Blum, Abdallah Boukerram


Given an undirected, vertex-weighted graph, the goal of the minimum weight vertex cover problem is to find a subset of the vertices of the graph such that the subset is a vertex cover and the sum of the weights of its vertices is minimal. This problem is known to be NP-hard and no efficient algorithm is known to solve it to optimality. Therefore, most existing techniques are based on heuristics for providing approximate solutions in a reasonable computation time. Population-based search approaches have shown to be effective for solving a multitude of combinatorial optimization problems. Their advantage can be identified as their ability to find areas of the space containing high quality solutions. This paper proposes a simple and efficient population-based iterated greedy algorithm for tackling the minimum weight vertex cover problem. At each iteration, a population of solutions is established and refined using a fast randomized iterated greedy heuristic based on successive phases of destruction and reconstruction. An extensive experimental evaluation on a commonly used set of benchmark instances shows that our algorithm outperforms current state-of-the-art approaches.



Wednesday, 13:45 - 14:10 h, Room: H 3012, Talk 2

Abderrezak Mohamed Djadoun
Random synchronized prospecting: A new metaheuristic for combinatorial optimization

Coauthor: Ilhem boussaid


In this contribution, we introduce Random Synchronized Prospecting(RSP), a new metaheuristic for solving NP-Hard combinatorial optimization problems.
This metaheuristic is presented as a swarm intelligence(SI) technique inspired by the way two groups of individuals would collaborate and exchange information while prospecting the solution's search space.
An example of the efficiency of this metaheuristic is presented by introducing the RSP-QAP algorithm, an adaptation of the RSP metaheuristic for the Quadratic Assignment Problem(QAP).
Computational results of applying the RSP-QAP algorithm to over 60 instances from the QAPLIB are shown.


  USA Payday Loans Online. In this section we give only a brief summary recommendation for admission of Canadian Levitra. Full information can be found in the instructions for receiving medications with vardenafil.