Surrogate constraint normalization for the set covering problem

DOI10.1016/j.ejor.2010.02.008zbMath1188.90205OpenAlexW2155693170MaRDI QIDQ976352

César Rego, Jose Humberto Ablanedo-Rosas

Publication date: 11 June 2010

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2010.02.008

zbMATH Keywords

heuristicsset covering problemsurrogate constraintsconstraint normalizationgreedy knapsack heuristic

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (7)

Optimizing word set coverage for multi-event summarization ⋮ Zero duality gap in surrogate constraint optimization: a concise review of models ⋮ What is the best greedy-like heuristic for the weighted set covering problem? ⋮ Three algorithms for graph locally harmonious colouring ⋮ Exploring further advantages in an alternative formulation for the set covering problem ⋮ A set covering approach for multi-depot train driver scheduling ⋮ Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems

Uses Software

• RAMP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using a facility location algorithm to solve large set covering problems
• Solving large set covering problems on a personal computer
• A probabilistic heuristic for a computationally difficult set covering problem
• An adaptation of SH heuristic to the location set covering problem
• Simple Lagrangian heuristic for the set covering problem
• Computational experience with approximation algorithms for the set covering problem
• A Lagrangian-based heuristic for large-scale set covering problems
• Clustering heuristics for set covering
• A set covering reformulation of the pure fixed charge transportation problem
• A surrogate heuristic for set covering problems
• Tutorial on surrogate constraint approaches for optimization in graphs
• A neural network for the minimum set covering problem
• Few statistical tests for proportions comparison
• An efficient heuristic for large set covering problems
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• Using Surrogate Constraints in a Lagrangian Relaxation Approach to Set-Covering Problems
• A note on some computationally difficult set covering problems
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• A Greedy Heuristic for the Set-Covering Problem
• Calculating surrogate constraints
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Surrogate Constraints in Integer Programming
• Surrogate Constraint Duality in Mathematical Programming
• On the hardness of approximating minimization problems
• A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering
• Genetic algorithms applied to computationally difficult set covering problems
• A Heuristic Method for the Set Covering Problem
• A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
• Surrogate Constraints
• Surrogate Mathematical Programming

This page was built for publication: Surrogate constraint normalization for the set covering problem