We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The main characteristics of the algorithm we propose are (1) a dynamic pricing scheme for the variables, akin to that used for solving large-scale LP's, to be coupled with subgradient optimization and greedy algorithms, and (2) the systematic use of column fixing to obtain improved solutions. Moreover, we propose a number of improvements on the standard way of defining the step-size and the ascent direction within the subgradient optimization procedure, and the scores within the greedy algorithms. Finally, an effective refining procedure is proposed. Extensive computational results show the effectiveness of the approach.

A heuristic algorithm for the set covering problem

Fischetti M.;
1996

Abstract

We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The main characteristics of the algorithm we propose are (1) a dynamic pricing scheme for the variables, akin to that used for solving large-scale LP's, to be coupled with subgradient optimization and greedy algorithms, and (2) the systematic use of column fixing to obtain improved solutions. Moreover, we propose a number of improvements on the standard way of defining the step-size and the ascent direction within the subgradient optimization procedure, and the scores within the greedy algorithms. Finally, an effective refining procedure is proposed. Extensive computational results show the effectiveness of the approach.
1996
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
5th International Conference Integer Programming and Combinatorial Optimization, IPCO 1996
978-3-540-61310-7
978-3-540-68453-4
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3389502
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? ND
  • OpenAlex ND
social impact