Algorithms for large scale set covering problems

DOI10.1007/BF02025297zbMath0784.90059OpenAlexW2025836060MaRDI QIDQ1309874

V. Pereyra

Publication date: 20 December 1993

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02025297

zbMATH Keywords

decompositionset coveringstate space relaxation

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Solving large set covering problems for crew scheduling, A structural Lagrangean relaxation for two-duty period bus driver scheduling problems, Graph theoretic relaxations of set covering and set partitioning problems, The multicovering problem, Lower bounds from state space relaxations for concave cost network flow problems, Improving set partitioning problem solutions by zooming around an improving direction, An adaptation of SH heuristic to the location set covering problem, An algorithm for set covering problem, A neural network for the minimum set covering problem, Algorithms for large scale set covering problems, State space relaxation for set covering problems related to bus driver scheduling

Uses Software

• XMP

Cites Work

• Unnamed Item
• Solving large set covering problems on a personal computer
• A probabilistic heuristic for a computationally difficult set covering problem
• A network relaxation based enumeration algorithm for set partitioning
• Dynamic versions of set covering type public facility location problems
• Algorithms for large scale set covering problems
• An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment
• The Backboard Wiring Problem: A Placement Algorithm
• Covering-Location Models for Emergency Situations That Require Multiple Response Units
• Optimal traffic assignment in a SS/TDMA frame : a new approach by set covering and column generation
• A Column Generation Approach to the Urban Transit Crew Scheduling Problem
• Some relationships between lagrangian and surrogate duality in integer programming
• Cutting planes from conditional bounds: A new approach to set covering
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• A Greedy Heuristic for the Set-Covering Problem
• A Lagrangean Relaxation Algorithm for the Two Duty Period Scheduling Problem
• State-space relaxation procedures for the computation of bounds to routing problems
• Calculating surrogate constraints
• Note—A Computational Survey of Methods for the Set Covering Problem
• An Integer Programming Approach to the Vehicle Scheduling Problem
• Set Partitioning: A survey
• The Set-Covering Problem: A New Implicit Enumeration Algorithm
• The Set-Partitioning Problem: Set Covering with Equality Constraints
• Optimal Political Districting by Implicit Enumeration Techniques
• Simplification of the Covering Problem with Application to Boolean Expressions
• Zero-one programming using non-binary tree-search
• Set Covering by Single-Branch Enumeration with Linear-Programming Subproblems
• Set Covering and Involutory Bases
• A Partitioning Problem with Applications in Regional Design