Solving large set covering problems on a personal computer (Q1097839): Difference between revisions

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.

0 references

Mathematics Subject Classification ID

90C27

0 references

0 references

0 references

0 references

set covering

0 references

NP-complete

0 references

heuristic

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0305-0548(88)90004-4

0 references

0 references

0 references

Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study

0 references

A Greedy Heuristic for the Set-Covering Problem

0 references

Computer Solutions to Minimum-Cover Problems

0 references

An efficient heuristic for large set covering problems

0 references

Using a facility location algorithm to solve large set covering problems

0 references

Hybrid heuristics for minimum cardinality set covering problems

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1097839

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0305-0548(88)90004-4
+Normal rank
@@ Property / OpenAlex ID @@
+W2048561128
@@ Property / OpenAlex ID: W2048561128 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4142699
@@ Property / cites work: Q4142699 / rank @@
+Normal rank
@@ Property / cites work @@
+Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
+Normal rank
@@ Property / cites work @@
+A Greedy Heuristic for the Set-Covering Problem
@@ Property / cites work: A Greedy Heuristic for the Set-Covering Problem / rank @@
+Normal rank
@@ Property / cites work @@
+Computer Solutions to Minimum-Cover Problems
@@ Property / cites work: Computer Solutions to Minimum-Cover Problems / rank @@
+Normal rank
@@ Property / cites work @@
+An efficient heuristic for large set covering problems
+Normal rank
@@ Property / cites work @@
+Using a facility location algorithm to solve large set covering problems
+Normal rank
@@ Property / cites work @@
+Hybrid heuristics for minimum cardinality set covering problems
+Normal rank