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

DOI10.1007/S10878-015-9935-1MaRDI QIDQ512865zbMATH OpenOpenAlexFDO

Authors 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) Combinatorial optimization (90C27) Mixed integer programming (90C11)

Recommendations

• Set covering with almost consecutive ones property
• Benders decomposition for very large scale partial set covering and maximal covering location problems
• Solving set covering problems of large dimension
• A-priori upper bounds for the set covering problem
• A novel decomposition approach to set covering problems by exploiting special structures

Cites work

• scientific article; zbMATH DE number 5859276 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2011862 (Why is no real title available?)
• scientific article; zbMATH DE number 3410784 (Why is no real title available?)
• A Benders decomposition approach for the locomotive and car assignment problem
• A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem
• A generalization of the weighted set covering problem
• A note on the NP-hardness of the consecutive block minimization problem
• A survey on Benders decomposition applied to fixed-charge network design problems
• A threshold of ln n for approximating set cover
• Algorithms for the set covering problem
• Algorithms – ESA 2004
• Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling
• Consecutive block minimization is 1.5-approximable
• Enhancing an algorithm for set covering problems
• Multicommodity Distribution System Design by Benders Decomposition
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• Partitioning procedures for solving mixed-variables programming problems
• Set covering with almost consecutive ones property
• Station location -- complexity and approximation
• THE CONTINUOUS STOP LOCATION PROBLEM IN PUBLIC TRANSPORTATION NETWORKS
• Tailoring Benders decomposition for uncapacitated network design
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The station location problem on two intersecting lines

Cited in

(7)

• A novel decomposition approach to set covering problems by exploiting special structures
• Set covering with almost consecutive ones property
• Iterated local search for consecutive block minimization
• Benders decomposition: solving binary master problems by enumeration
• Exact and heuristic algorithms for the maximum weighted submatrix coverage problem
• A nested decomposition approach for a large scale set covering problem: a model with a variety of applications in Industry 4.0
• Efficient heuristics for a partial set covering problem with mutually exclusive pairs of facilities

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q512865)