A 3-flip neighborhood local search for the set covering problem

DOI10.1016/j.ejor.2004.10.018zbMath1120.90025OpenAlexW2039862033MaRDI QIDQ2490164

Toshihide Ibaraki, Masahiro Kishida, Mutsunori Yagiura

Publication date: 28 April 2006

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

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

zbMATH Keywords

Lagrangian relaxationSet covering problemMetaheuristicsStrategic oscillationLarge neighborhood

Mathematics Subject Classification ID

Search theory (90B40) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

An efficient local search heuristic with row weighting for the unicost set covering problem, A distance-limited continuous location-allocation problem for spatial planning of decentralized systems, Relaxation heuristics for the set multicover problem with generalized upper bound constraints, The robust set covering problem with interval data, A hybrid heuristic for the set covering problem, A GRASP algorithm to solve the unicost set covering problem, A variable neighborhood search algorithm for the multimode set covering problem, MLQCC: an improved local search algorithm for the set k‐covering problem, Exploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs, RAMP for the capacitated minimum spanning tree problem, An improved configuration checking-based algorithm for the unicost set covering problem, Solving the wire-harness design problem at a European car manufacturer, An electromagnetism metaheuristic for the unicost set covering problem, A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation, The set covering problem revisited: an empirical study of the value of dual information, A new approach for solving set covering problem using jumping particle swarm optimization method, A set covering approach for multi-depot train driver scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Improved solutions to the Steiner triple covering problem
• Using a facility location algorithm to solve large set covering problems
• A probabilistic heuristic for a computationally difficult set covering problem
• Enhancing an algorithm for set covering problems
• A genetic algorithm for the set covering problem
• Simple Lagrangian heuristic for the set covering problem
• A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems
• A Lagrangian-based heuristic for large-scale set covering problems
• Logical analysis of numerical data
• An efficient tabu search approach for the 0-1 multidimensional knapsack problem
• An algorithm for set covering problem
• Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT: experimental Evaluation
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• Tabu Search—Part I
• A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering
• An indirect genetic algorithm for set covering problems
• Note: A local-search heuristic for large set-covering problems
• A Heuristic Method for the Set Covering Problem
• The traveling-salesman problem and minimum spanning trees: Part II