Exploiting fitness distance correlation of set covering problems

Markus Finger, Thomas Stützle and Helena Ramalhinho-Lourenço ()
Additional contact information
Helena Ramalhinho-Lourenço: https://www.upf.edu/web/econ/faculty/-/asset_publisher/6aWmmXf28uXT/persona/id/3418484

Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra

Abstract: The set covering problem is an NP-hard combinatorial optimization problem that arises in applications ranging from crew scheduling in airlines to driver scheduling in public mass transport. In this paper we analyze search space characteristics of a widely used set of benchmark instances through an analysis of the fitness-distance correlation. This analysis shows that there exist several classes of set covering instances that have a largely different behavior. For instances with high fitness distance correlation, we propose new ways of generating core problems and analyze the performance of algorithms exploiting these core problems.

Keywords: Set covering; iterated local search (search for similar items in EconPapers)
JEL-codes: C61 C63 D83 (search for similar items in EconPapers)
Date: 2001-11
New Economics Papers: this item is included in nep-ent and nep-net
References: Add references at CitEc
Citations:

Downloads: (external link)
https://econ-papers.upf.edu/papers/582.pdf Whole Paper (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:upf:upfgen:582

Access Statistics for this paper

More papers in Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra
Bibliographic data for series maintained by ( this e-mail address is bad, please contact ).