Solving large set covering problems on a personal computer

DOI10.1016/0305-0548(88)90004-4MaRDI QIDQ1097839zbMATH OpenOpenAlexFDO

Authors Francis J. Vasko, Floyd E. Wolf

Publication date 1988

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0305-0548(88)90004-4

zbMATH Keywords

heuristicNP-completeset covering

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Combinatorial optimization (90C27)

Review text

The set covering problem (SCP) was one of the first problems shown to be NP-complete. Heuristics are commonly used on mainframe computers in order to efficiently solve large-scale SCPs. In this paper, we use a new heuristic and several existing heuristics written in FORTRAN to solve 31 large (up to 2000 variables) SCPs on an IBM PC/AT. The new heuristic, SCAMP (set covering algorithm for the microprocessor), performed the best, with solution values deviating only in average 1,8 \% from the optimum.

Recommendations

• Algorithms for large scale set covering problems
• Note: A local-search heuristic for large set-covering problems
• A heuristic algorithm for the set covering problem
• A two-phase heuristic for set covering
• RELAXATION HEURISTICS FOR THE SET COVERING PROBLEM(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• An efficient heuristic for large set covering problems
• Computer Solutions to Minimum-Cover Problems
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• Hybrid heuristics for minimum cardinality set covering problems
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• Using a facility location algorithm to solve large set covering problems

Cited in

(10)

• Algorithms for large scale set covering problems
• A column generation approach to job grouping for flexible manufacturing systems
• A surrogate heuristic for set covering problems
• Hybrid heuristics for minimum cardinality set covering problems
• scientific article; zbMATH DE number 4106856 (Why is no real title available?)
• Note: A local-search heuristic for large set-covering problems
• Using a facility location algorithm to solve large set covering problems
• Solution techniques for the large set covering problem
• Solving the set cover problem on a supercomputer
• Surrogate constraint normalization for the set covering problem

This page was built for publication: Solving large set covering problems on a personal computer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1097839)