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

DOI10.1007/BFB0120886zbMath0435.90074OpenAlexW1573881838MaRDI QIDQ3875704

No author found.

Publication date: 1980

Published in: Mathematical Programming Studies (Search for Journal in Brave)

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

zbMATH Keywords

branch and boundlower boundsimplementationbranching rulescomputational studycomparison of algorithmssubgradient optimizationimplicit enumerationrandom test problemsprime coversconditional boundscomputational testingcutting planes, heuristicsset covering algorithms

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (93)

Average and worst-case analysis of heuristics for the maximum tardiness problem ⋮ The continuousm-center problem on a network ⋮ The column subtraction algorithm: An exact method for solving weighted set covering, packing and partitioning problems ⋮ A column generation approach to job grouping for flexible manufacturing systems ⋮ A surrogate heuristic for set covering problems ⋮ Entropy and set covering ⋮ Two new heuristics for the location set covering problem ⋮ On some difficult linear programs coming from set partitioning ⋮ Two-phase method and Lagrangian relaxation to solve the bi-objective set covering problem ⋮ Solving large set covering problems on a personal computer ⋮ Hybrid heuristics for minimum cardinality set covering problems ⋮ Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems ⋮ A new approach for crew pairing problems by column generation with an application to air transportation ⋮ An efficient local search heuristic with row weighting for the unicost set covering problem ⋮ Set covering problem with conflict constraints ⋮ An algorithm for large scale 0-1 integer programming with application to airline crew scheduling ⋮ A packet filter placement problem with application to defense against spoofed denial of service attacks ⋮ A finite procedure to generate feasible points for the extreme point mathematical programming problem ⋮ A generalized model and a heuristic algorithm for the large-scale covering tour problem ⋮ Algorithms for railway crew management ⋮ Logical analysis of numerical data ⋮ A class of manpower scheduling problems ⋮ Solving large set covering problems for crew scheduling ⋮ The bi-objective covering tour problem ⋮ Learning pseudo-backdoors for mixed integer programs ⋮ Solving a bicriteria problem of optimal service centers location ⋮ A structural Lagrangean relaxation for two-duty period bus driver scheduling problems ⋮ On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\) ⋮ On the 0,1 facets of the set covering polytope ⋮ On the facial structure of the set covering polytope ⋮ A probabilistic heuristic for a computationally difficult set covering problem ⋮ Facets and lifting procedures for the set covering polytope ⋮ Probabilistic partial set covering problems ⋮ A comparison of algorithm RS with algorithm OPTSOL70 ⋮ On a linearization technique for solving the quadratic set covering problem and variations ⋮ Solving hard set covering problems ⋮ Graph theoretic relaxations of set covering and set partitioning problems ⋮ The design of a 0-1 integer optimizer and its application in the Carmen system ⋮ Continuous cutting plane algorithms in integer programming ⋮ Matheuristics: survey and synthesis ⋮ Column elimination for capacitated vehicle routing problems ⋮ Automatic generation of dominance breaking nogoods for a class of constraint optimization problems ⋮ Efficient heuristics for a partial set covering problem with mutually exclusive pairs of facilities ⋮ Hybrid heuristic algorithms for set covering. ⋮ Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty ⋮ A finite cutting plane method for solving linear programs with an additional reverse convex constraint ⋮ Conditional clusters, musters, and probability ⋮ Absolute bounds on optimal cost for a class of set covering problems ⋮ Exact algorithms for the vertex separator problem in graphs ⋮ A heuristic algorithm for the set covering problem ⋮ Enhancing an algorithm for set covering problems ⋮ A matheuristic based on Lagrangian relaxation for the multi-activity shift scheduling problem ⋮ An efficient heuristic for large set covering problems ⋮ The multicovering problem ⋮ Determination of minimum number of sensors and their locations for an automated facility: An algorithmic approach ⋮ An integer programming-based local search for the covering salesman problem ⋮ Cutting planes in integer and mixed integer programming ⋮ Set covering-based surrogate approach for solving sup-\({\mathcal{T}}\) equation constrained optimization problems ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ Un nuevo resultado sobre la complejidad del problema delP-centro ⋮ A 3-flip neighborhood local search for the set covering problem ⋮ Surrogate constraint normalization for the set covering problem ⋮ Algorithms for solving the conditional covering problem on paths ⋮ Heuristic solutions and confidence intervals for the multicovering problem ⋮ Set covering approach for reconstruction of sibling relationships ⋮ Iterative Column Generation Algorithm for Generalized Multi-Vehicle Covering Tour Problem ⋮ Fast heuristics for large scale covering-location problems ⋮ A multi-objective integrated facility location-hardening model: analyzing the pre- and post-disruption tradeoff ⋮ The Generalized Covering Salesman Problem ⋮ Semi-greedy heuristics: An empirical study ⋮ An adaptation of SH heuristic to the location set covering problem ⋮ A genetic algorithm for the set covering problem ⋮ Computational experience with approximation algorithms for the set covering problem ⋮ An algorithm for set covering problem ⋮ Heuristic methods and applications: A categorized survey ⋮ A parallel variable neighborhood search for solving covering salesman problem ⋮ A Lagrangian-based heuristic for large-scale set covering problems ⋮ A neural network for the minimum set covering problem ⋮ Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems ⋮ A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles ⋮ Note: A local-search heuristic for large set-covering problems ⋮ A new reformulation approach for the generalized partial covering problem ⋮ Network models for vehicle and crew scheduling ⋮ Using a facility location algorithm to solve large set covering problems ⋮ Algorithms for large scale set covering problems ⋮ Pareto optimality and a class of set covering heuristics ⋮ Clustering heuristics for set covering ⋮ A set covering approach for multi-depot train driver scheduling ⋮ Column generation extensions of set covering greedy heuristics ⋮ Experiments with parallel branch-and-bound algorithms for the set covering problem ⋮ Worst case analysis of a class of set covering heuristics ⋮ State space relaxation for set covering problems related to bus driver scheduling ⋮ A tabu search approach to the constraint satisfaction problem as a general problem solver

This page was built for publication: Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study