Solving the non-unicost set covering problem by using cuckoo search and black hole optimization

Ricardo Soto, Broderick Crawford, Rodrigo Olivares, Jorge Barraza, Ignacio Figueroa, Franklin Johnson, Fernando Paredes, Eduardo Olguín

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

The set covering problem is a classical optimization benchmark that finds application in several real-world domains, particularly in line balancing production, crew scheduling, and service installation. The problem consists in finding a subset of columns in a zero-one matrix such that they cover all the rows of the matrix at a minimum cost. In this paper, we present two new approaches for efficiently solving this problem, the first one based on cuckoo search and the second one on black hole optimization. Both are relatively modern bio-inspired metaheuristics that have attracted much attention due to their rapid convergence, easy implementation, and encouraging obtained results. We integrate to the core of both metaheuristics an effective pre-processing phase as well as multiple transfer functions and discretization methods. Pre-processing is employed for filtering the values from domains leading to infeasible solutions, while transfers function and discretization methods are used for efficiently handling the binary nature of the problem. We illustrate interesting experimental results where the two proposed approaches are able to obtain various global optimums for a set of well-known set covering problem instances, outperforming also several recently reported techniques.

Original languageEnglish
Pages (from-to)213-229
Number of pages17
JournalNatural Computing
Volume16
Issue number2
DOIs
StatePublished - 1 Jun 2017
Externally publishedYes

Keywords

  • Bio-inspired
  • Black hole
  • Cuckoo search
  • Metaheuristic
  • Set covering problem

Fingerprint

Dive into the research topics of 'Solving the non-unicost set covering problem by using cuckoo search and black hole optimization'. Together they form a unique fingerprint.

Cite this