A Lagrangian-based heuristic for large-scale set covering problems

We present a new Lagrangian-based heuristic for solving large-scale set-covering problems arising from crew-scheduling at the Italian Railways (Ferrovie dello Stato). Our heuristic obtained impressive results when compared to state-of-the-art codes on a test-bed provided by the company, which includes instances with sizes ranging from 50,000 variables and 500 constraints to 1,000,000 variables and 5000 constraints. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.This research was performed while the author was affiliated with IASI, CNR and Dipartimento di Informatica e Sistemistica, Università di Roma, La Sapienza, Italy.This research was partially supported by National Research Program Metodi di Ottimizzazione per le Decisioni, MURST, Roma, Italy.