The impact of a new formulation when solving the set covering problem using the ACO metaheuristic

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

The Set Covering Problem (SCP) is a well-known NP hard discrete optimization problem that has been applied to a wide range of industrial applications, including those involving scheduling, production planning and location problems. The main difficulties when solving the SCP with a metaheuristic approach are the solution infeasibility and set redundancy. In this paper we evaluate a state of the art new formulation of the SCP which eliminates the need to address the infeasibility and set redundancy issues. The experimental results, conducted on a portfolio of SCPs from the Beasley’s OR-Library, show the gains obtained when using a new formulation to solve the SCP using the ACO metaheuristic.

Original languageEnglish
Title of host publicationModelling, Computation and Optimization in Information Systems and Management Sciences - Proceedings of the 3rd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, MCO 2015 - Part II
EditorsHoai An Le Thi, Ngoc Thanh Nguyen, Tao Pham Dinh
PublisherSpringer Verlag
Pages209-218
Number of pages10
ISBN (Print)9783319181660
DOIs
StatePublished - 1 Jan 2015
Event3rd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, MCO 2015 - Nancy, France
Duration: 11 May 201513 May 2015

Publication series

NameAdvances in Intelligent Systems and Computing
Volume360
ISSN (Print)2194-5357

Conference

Conference3rd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, MCO 2015
Country/TerritoryFrance
CityNancy
Period11/05/1513/05/15

Keywords

  • Ant Colony Optimization
  • Metaheuristics
  • Set Covering Problem

Fingerprint

Dive into the research topics of 'The impact of a new formulation when solving the set covering problem using the ACO metaheuristic'. Together they form a unique fingerprint.

Cite this