Computer Solutions to Minimum-Cover Problems

R. Roth
R. Roth
Bell Telephone Laboratories, Inc., Murray Hill, New Jersey
Search for more papers by this author

Bell Telephone Laboratories, Inc., Murray Hill, New Jersey

Published Online:1 Jun 1969https://doi.org/10.1287/opre.17.3.455

Abstract

A covering problem may be stated as follows:

An algorithm has been programmed on the IBM 7094 for solving such problems. For a given problem, it generates a set of independent “locally-optimum” solutions. If p is the probability that any one solution is actually an optimum, then for n independently generated solutions we have a prob-babiiity of 1−(1 − p)ⁿ that an optimal solution appears in the set generated. Computational experience indicates that this approach yields good results for large problems (up to m · n ≦ 0.5 × 10⁶).

Cited by
- Multi-objective evolutionary algorithms and integer programming for the optimization of underwater acoustic sensor network design
  Applied Soft Computing, Vol. 191
- A Demand-based Methodology for Urban Rail Transit Express Line Problem using Metaheuristic
  26 June 2025 | Networks and Spatial Economics, Vol. 25, No. 4
- 20712 Entropy based emergency rescue location selection with uncertain travel time
- Maritime accidents-based optimal rescue ship location using dynamic programming and particle swarm optimisation algorithm
  12 March 2025 | Journal of Navigation, Vol. 25
- Breaking Symmetries from a Set-Covering Perspective
  29 June 2025
- Data driven multi-objective optimization of sustainable aviation emergency network for forest fire rescue
  Sustainable Operations and Computers, Vol. 6
- Optimization for regional examination centers design considering multiservice collaboration *
- Spatial Allocation of Shelters Considering the Blockage Effect on Roads during an Earthquake
  Natural Hazards Review, Vol. 25, No. 1
- Exploring the comprehensive optimization model for location strategy of bridging depots based on metro vulnerability and information entropy
- Multiobjective Electric Vehicle Charging Network Planning Considering Chance‐Constraint on the Travel Distance for Charging
  17 November 2023 | IET Electrical Systems in Transportation, Vol. 2023, No. 1
- Optimization of Multi-Objective Mobile Emergency Material Allocation for Sudden Disasters
  14 July 2022 | Frontiers in Public Health, Vol. 10
- An Optimization Method of Sports Service Network Layout Based on Network Communication
  Mathematical Problems in Engineering, Vol. 2022
- Optimal location of water level sensors for monitoring mine water inrush based on the set covering model
  29 January 2021 | Scientific Reports, Vol. 11, No. 1
- Using Taxi GPS Trajectory Data to Optimize the Spatial Layout of Urban Taxi Stands
  31 December 2020 | Transportation Research Record: Journal of the Transportation Research Board, Vol. 2675, No. 3
- Location problem of Osmia cornuta nesting aids for optimum pollination
  31 December 2020 | PLOS ONE, Vol. 15, No. 12
- Study on the Allocation of a Rescue Base in the Arctic
  24 August 2019 | Symmetry, Vol. 11, No. 9
- Planning Emergency Shelters for Urban Disasters: A Multi-Level Location–Allocation Modeling Approach
  8 August 2019 | Sustainability, Vol. 11, No. 16
- Covering Location Problems
  17 March 2020
- Classic Beginnings
  23 December 2018
- Selecting China’s strategic petroleum reserve sites by multi-objective programming model
  22 July 2017 | Petroleum Science, Vol. 14, No. 3
- A study on test nodes selection problem with test capacity constraint in QoE measurement network
- Integrated Modeling for Location Analysis
  18 October 2016 | Foundations and Trends in Technology, Information and Operations Management, Vol. 9, No. 1-2
- Relationship Between Set Covering Location and Maximal Covering Location Problems in Facility Location Application
  11 March 2016
- Contrastive Analysis of Heuristic Algorithms for Covering Location Model of Traffic Patrol Police Deployment
- Location Planning Problem of Service Centers for Sustainable Home Healthcare: Evidence from the Empirical Analysis of Shanghai
  27 November 2015 | Sustainability, Vol. 7, No. 12
- A Specific Heuristic Dedicated to a Coverage/Tracking Bi-objective Problem for Wireless Sensor Deployment
  3 April 2015 | Wireless Personal Communications, Vol. 84, No. 3
- Linearization approach to multi objective set covering problem with imprecise nonlinear fractional objectives
  13 January 2015 | OPSEARCH, Vol. 52, No. 3
- Covering Location Problems
  21 January 2015
- Emergency Rescue Location Model with Uncertain Rescue Time
  1 December 2014 | Mathematical Problems in Engineering, Vol. 2014, No. 1
- Research on Location-Inventory Model in Grain Emergency Network
  Journal of Computer and Communications, Vol. 02, No. 14
- Coordination of repeaters based on Simulated Annealing Algorithm and Monte-Carlo Algorithm
  Neurocomputing, Vol. 97
- Covering problems in facility location: A review
  Computers & Industrial Engineering, Vol. 62, No. 1
- Relation between set partitioning and set covering problems with quadratic fractional objective functions
  18 October 2011 | OPSEARCH, Vol. 48, No. 3
- Research on minimum cost location problem of emergency material storage
- Enumeration technique for solving multi-objective quadratic set-covering problem using goal programming
  2 May 2011 | OPSEARCH, Vol. 48, No. 1
- Placement of Synchronized Measurements for Power System Observability
  IEEE Transactions on Power Delivery, Vol. 24, No. 1
- A Location Programming under Stochastic Travel Time through Genetic Algorithm
- Geography in Coverage Modeling: Exploiting Spatial Structure to Address Complementary Partial Service of Areas
  Annals of the Association of American Geographers, Vol. 95, No. 4
- A Goal Programming Approach to Solve Linear Fractional Multi-Objective Set Covering Problem
  14 December 2017 | OPSEARCH, Vol. 42, No. 2
- A genetic algorithm for time-satisfaction-based set covering location problems
- The Multi‐level Location Set Covering Model
  16 November 2010 | Geographical Analysis, Vol. 35, No. 4
- Strategic analysis of public transport coverage
  Socio-Economic Planning Sciences, Vol. 35, No. 3
- Applications of Set Covering, Set Packing and Set Partitioning Models: A Survey
- A comparison of algorithm RS with algorithm OPTSOL70
  Top, Vol. 5, No. 2
- An adaptation of SH heuristic to the location set covering problem
  European Journal of Operational Research, Vol. 100, No. 3
- Scheduling tests for VLSI systems under power constraints
  IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 5, No. 2
- Multiobjective Covering and Routing Problems
- A Linearization technique for solving the quadratic set covering problem
  Optimization, Vol. 39, No. 1
- On Haar's dual problem
  OR Spektrum, Vol. 18, No. 4
- TEST SCHEDULING IN TESTABLE VLSI CIRCUITS
- Two new heuristics for the location set covering problem
  Top, Vol. 2, No. 2
- Power constraint scheduling of tests
- The use of hill‐climbing to construct orthogonal steiner triple systems
  14 November 2006 | Journal of Combinatorial Designs, Vol. 1, No. 1
- An optimal method for solving the (generalized) multi-Weber problem
  European Journal of Operational Research, Vol. 58, No. 3
- A lagrangian heuristic for set-covering problems
  Naval Research Logistics, Vol. 37, No. 1
- Solving large set covering problems on a personal computer
  Computers & Operations Research, Vol. 15, No. 2
- Randomized algorithms in combinatorial optimization: A survey
  Discrete Applied Mathematics, Vol. 14, No. 2
- Bayesian nonparametrie inference and monte carlo optimization
  Optimization, Vol. 17, No. 5
- Minimal covering problem and PLA minimization
  International Journal of Computer & Information Sciences, Vol. 14, No. 6
- Randomized algorithms: An annotated bibliography
  Annals of Operations Research, Vol. 1, No. 3
- Using a facility location algorithm to solve large set covering problems
  Operations Research Letters, Vol. 3, No. 2
- SYMPOSIUM ON LOCATION PROBLEMS: IN MEMORY OF LEON COOPER
  28 July 2006 | Journal of Regional Science, Vol. 24, No. 2
- An efficient heuristic for large set covering problems
  10 October 2006 | Naval Research Logistics Quarterly, Vol. 31, No. 1
- A set-covering problem: the combinatorial-local approach and the branch and bound method
  USSR Computational Mathematics and Mathematical Physics, Vol. 19, No. 6
- Literaturverzeichnis
- Optimierungsprobleme mit Nicht Polynomial Begrenzten Algorithmen
- Algorithmic Techniques for the Generation and Analysis of Strongly Regular Graphs and other Combinatorial Configurations
- Heuristic Programming as an Aid to Network Design
  11 October 2006 | Networks, Vol. 5, No. 1
- References††The first comprehensive references list is due to Balinski and Spielberg (1969). A later list appears in the work of Garfinkel and Nemhauser (1972b).
- Hierarchical location analysis for integrated area planning in Rural India
  Papers of the Regional Science Association, Vol. 33, No. 1
- On Covering Problems and the Central Facilities Location Problem
  3 September 2010 | Geographical Analysis, Vol. 6, No. 3
- An Efficient Algorithm for Finding an Irredundant Set Cover
  1 July 1974 | Journal of the ACM, Vol. 21, No. 3
- Heuristically aided set-covering algorithms
  International Journal of Computer & Information Sciences, Vol. 3, No. 1
- A method of bad data detection for power system state estimation
  19 April 2007 | Electrical Engineering in Japan, Vol. 94, No. 2
- Topics in computer‐aided design: Part I. An optimum tearing algorithm for recycle systems
  17 June 2004 | AIChE Journal, Vol. 19, No. 6
- A rationale for heuristic program selection and evaluation
  1 July 1973 | ACM SIGDA Newsletter, Vol. 3, No. 1-2
- Binary Logic Solutions to a Class of Location Problem*
  3 September 2010 | Geographical Analysis, Vol. 5, No. 2
- On The Set Representation and Set Covering Problems
- Optimal location under time or distance constraints
  Papers of the Regional Science Association, Vol. 28, No. 1
- On Finding the Paths Through a Network
  29 July 2013 | Bell System Technical Journal, Vol. 51, No. 2
- A fundamental problem in linear inequalities with applications to the travelling salesman problem
  Mathematical Programming, Vol. 2, No. 1
- Un problème de recouvrement : l'habillage des horaires d'une ligne d'autobus
  29 March 2011 | Revue française d'automatique, informatique, recherche opérationnelle. Recherche opérationnelle, Vol. 6, No. V1
- The set covering problem : a group theoretic approach
  29 March 2011 | Revue française d'informatique et de recherche opérationnelle. Série verte, Vol. 5, No. V3
- An Approach to Solving Linear Discrete Optimization Problems
  1 April 1970 | Journal of the ACM, Vol. 17, No. 2

Volume 17, Issue 3

May-June 1969

Pages 373-556

Article Information

Metrics

Information

Published Online:June 01, 1969

Cite as

R. Roth, (1969) Computer Solutions to Minimum-Cover Problems. Operations Research 17(3):455-465.

https://doi.org/10.1287/opre.17.3.455

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Computer Solutions to Minimum-Cover Problems

Abstract

Volume 17, Issue 3

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News