This paper introduces the multi-mode set covering problem, which consists of a plurality of set covering problems linked by cardinality constraints. We propose a variable neighborhood search algorithm and a greedy randomized adaptive search procedure based on a common local search routine. This routine applies a penalized relaxation of the covering constraints, tuned by self-adapting parameters, and visits a sequence of neighborhoods in a nested strategy. We compare the two heuristics with each other and with a time-limited run of a general-purpose integer linear programming solver, on a benchmark set of instances with heterogeneous structure. Both heuristics outperform the solver, though with interesting differences with respect to the various classes of instances. In particular, the variable neighborhood search algorithm proves more effective and less dependent on the specific features of the instances.

Colombo, F., Cordone, R., Lulli, G. (2015). A variable neighborhood search algorithm for the multimode set covering problem. JOURNAL OF GLOBAL OPTIMIZATION, 63(3), 461-480 [10.1007/s10898-013-0094-6].

A variable neighborhood search algorithm for the multimode set covering problem

Lulli, G
2015

Abstract

This paper introduces the multi-mode set covering problem, which consists of a plurality of set covering problems linked by cardinality constraints. We propose a variable neighborhood search algorithm and a greedy randomized adaptive search procedure based on a common local search routine. This routine applies a penalized relaxation of the covering constraints, tuned by self-adapting parameters, and visits a sequence of neighborhoods in a nested strategy. We compare the two heuristics with each other and with a time-limited run of a general-purpose integer linear programming solver, on a benchmark set of instances with heterogeneous structure. Both heuristics outperform the solver, though with interesting differences with respect to the various classes of instances. In particular, the variable neighborhood search algorithm proves more effective and less dependent on the specific features of the instances.
Articolo in rivista - Articolo scientifico
Greedy randomized adaptive search procedure; Set covering problem; Variable neighborhood search;
Set Covering Problem, Variable Neighborhood Search
English
2015
63
3
461
480
reserved
Colombo, F., Cordone, R., Lulli, G. (2015). A variable neighborhood search algorithm for the multimode set covering problem. JOURNAL OF GLOBAL OPTIMIZATION, 63(3), 461-480 [10.1007/s10898-013-0094-6].
File in questo prodotto:
File Dimensione Formato  
JOGO_2015.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 839.43 kB
Formato Adobe PDF
839.43 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/10281/49038
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 7
Social impact