## 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**

**Abstract:**

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**

**Abstract:**

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.