An improved hybrid algorithm for the set covering problem |
| |
Affiliation: | 1. V.A. Trapeznikov Institute of Control Science of Russian Academy of Sciences, Profsoyuznaya st. 65, 117997 Moscow, Russia;2. Ecole Nationale Superieure des Mines, CNRS UMR6158, LIMOS, F-42023 Saint-Etienne, France;3. Lomonosov Moscow State University, GSP-1, Leninskie Gory, Moscow, 119991, Russia;4. Moscow Institute of Physics and Technology, 9 Institutskiy per., Dolgoprudny, Moscow Region, 141700, Russia;5. International Laboratory of Decision Choice and Analysis, National Research University Higher School of Economics, 20 Myasnsnitskaya st., 101000 Moscow, Russia;1. Department of mathematics and computer sciences,Ziane Achour University, Djelfa 17000, Algeria;2. Faculty of sciences, Abderrahmane Mira University, Béjaïa 06000, Algeria |
| |
Abstract: | The state-of-the-art ant colony optimization (ACO) algorithm to solve large scale set covering problems (SCP) starts by solving the Lagrangian dual (LD) problem of the SCP to obtain quasi-optimal dual values. These values are then exploited by the ACO algorithm in the form of heuristic estimates. This article starts by discussing the complexity of this approach where a number of new parameters are introduced to escape local optimums and normalize the heuristic values. To avoid these complexities, we propose a new hybrid algorithm that starts by solving the linear programming (LP) relaxation of the SCP. This solution is used to eliminate unnecessary columns, and to estimate the heuristic information. To generate solutions, we use a Max–Min Ant System (MMAS) algorithm that employs a novel mechanism to update the pheromone trail limits to maintain a predetermined exploration rate. Computational experiments on different sets of benchmark instances prove that our proposed algorithm can be considered the new state-of-the-art meta-heuristic to solve the SCP. |
| |
Keywords: | Linear programming Lagrangian relaxation Max–min ant system Ant colony optimization Set covering problem |
本文献已被 ScienceDirect 等数据库收录! |
|