[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article

A Heuristic Method for the Set Covering Problem

Published: 01 May 1999 Publication History

Abstract

We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The algorithm was initially designed for solving very large scale SCP instances, involving up to 5,000 rows and 1,000,000 columns, arising from crew scheduling in the Italian Railway Company, Ferrovie dello Stato SpA. In 1994 Ferrovie dello Stato SpA, jointly with the Italian Operational Research Society, organized a competition, called FASTER, intended to promote the development of algorithms capable of producing good solutions for these instances, since the classical approaches meet with considerable difficulties in tackling them. 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 LPs, 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. Our code won the first prize in the FASTER competition, giving the best solution value for all the proposed instances. The algorithm was also tested on the test instances from the literature: in 92 out of the 94 instances in our test bed we found, within short computing time, the optimal (or the best known) solution. Moreover, among the 18 instances for which the optimum is not known, in 6 cases our solution is better than any other solution found by previous techniques.

Cited By

View all
  • (2023)A Lagrangian relaxation approach to an electricity system investment model with a high temporal resolutionOR Spectrum10.1007/s00291-023-00736-w45:4(1263-1294)Online publication date: 1-Dec-2023
  • (2022)Robust min-max regret covering problemsComputational Optimization and Applications10.1007/s10589-022-00391-x83:1(111-141)Online publication date: 1-Sep-2022
  • (2021)Solutions for the Deployment of Communication Roadside Infrastructure for Streaming Delivery in Vehicular NetworksJournal of Network and Systems Management10.1007/s10922-021-09600-029:3Online publication date: 1-Jul-2021
  • Show More Cited By
  1. A Heuristic Method for the Set Covering Problem

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image Operations Research
    Operations Research  Volume 47, Issue 5
    May 1999
    141 pages

    Publisher

    INFORMS

    Linthicum, MD, United States

    Publication History

    Published: 01 May 1999

    Author Tags

    1. Programming
    2. heuristic algorithm
    3. integer
    4. set covering

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 20 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)A Lagrangian relaxation approach to an electricity system investment model with a high temporal resolutionOR Spectrum10.1007/s00291-023-00736-w45:4(1263-1294)Online publication date: 1-Dec-2023
    • (2022)Robust min-max regret covering problemsComputational Optimization and Applications10.1007/s10589-022-00391-x83:1(111-141)Online publication date: 1-Sep-2022
    • (2021)Solutions for the Deployment of Communication Roadside Infrastructure for Streaming Delivery in Vehicular NetworksJournal of Network and Systems Management10.1007/s10922-021-09600-029:3Online publication date: 1-Jul-2021
    • (2021)Efficient feature selection for logical analysis of large-scale multi-class datasetsJournal of Combinatorial Optimization10.1007/s10878-021-00732-242:1(1-23)Online publication date: 1-Jul-2021
    • (2020)Algorithms and Applications to Weighted Rank-one Binary Matrix FactorizationACM Transactions on Management Information Systems10.1145/338659911:2(1-33)Online publication date: 3-May-2020
    • (2020)A binary monkey search algorithm variation for solving the set covering problemNatural Computing: an international journal10.1007/s11047-019-09752-819:4(825-841)Online publication date: 1-Dec-2020
    • (2020)A Memetic Approach for the Unicost Set Covering ProblemLearning and Intelligent Optimization10.1007/978-3-030-53552-0_23(233-248)Online publication date: 24-May-2020
    • (2019)A Db-Scan Binarization Algorithm Applied to Matrix Covering ProblemsComputational Intelligence and Neuroscience10.1155/2019/32385742019Online publication date: 1-Jan-2019
    • (2019)Ants for Identifying and Optimizing the Core Set K-Covering Problem2019 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2019.8790212(2552-2558)Online publication date: 10-Jun-2019
    • (2018)Optimal Course Scheduling for United States Air Force Academy CadetsInterfaces10.1287/inte.2017.093548:3(217-234)Online publication date: 1-Jun-2018
    • Show More Cited By

    View Options

    View options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media