Benders decomposition for set covering problems. Almost satisfying the consecutive ones property

DOI10.1007/s10878-015-9935-1zbMath1364.90290OpenAlexW1859428181MaRDI QIDQ512865

Yong-Cai Geng, Sumit K. Garg

Publication date: 3 March 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-015-9935-1

zbMATH Keywords

set coveringbenders decompositionconsecutive ones propertyconsecutive block minimisation

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Mixed integer programming (90C11) Combinatorial optimization (90C27)

Related Items (3)

Iterated local search for consecutive block minimization ⋮ Efficient heuristics for a partial set covering problem with mutually exclusive pairs of facilities ⋮ A Nested Decomposition Approach for a Large Scale Set Covering Problem: A Model with a Variety of Applications in Industry 4.0

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Consecutive block minimization is 1.5-approximable
• Partitioning procedures for solving mixed-variables programming problems
• Enhancing an algorithm for set covering problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A survey on Benders decomposition applied to fixed-charge network design problems
• A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem
• Set covering with almost consecutive ones property
• A Benders Decomposition Approach for the Locomotive and Car Assignment Problem
• Station Location - Complexity and Approximation.
• A threshold of ln n for approximating set cover
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• THE CONTINUOUS STOP LOCATION PROBLEM IN PUBLIC TRANSPORTATION NETWORKS
• Tailoring Benders decomposition for uncapacitated network design
• Multicommodity Distribution System Design by Benders Decomposition
• Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling
• A note on the NP-hardness of the consecutive block minimization problem
• A generalization of the weighted set covering problem
• Algorithms – ESA 2004
• Algorithms for the set covering problem

This page was built for publication: Benders decomposition for set covering problems. Almost satisfying the consecutive ones property