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

DOI10.1007/S10878-015-9935-1zbMATH Open1364.90290OpenAlexW1859428181MaRDI QIDQ512865FDOQ512865

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

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

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)

Cites Work

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

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
• 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

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)