Benders decomposition for set covering problems

详细信息    查看全文

• 作者：S. Haddadi
• 关键词：Set covering ; Benders decomposition ; Consecutive block minimisation ; Consecutive ones property
• 刊名：Journal of Combinatorial Optimization
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：33
• 期：1
• 页码：60-80
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Theory of Computation; Optimization; Operation Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2886
• 卷排序：33

文摘

This paper describes Benders decomposition approaches to optimally solve set covering problems “ almost” satisfying the consecutive ones property. The decompositions are based on the fact that set covering problems with consecutive ones property have totally unimodular coefficient matrices. Given a binary matrix, a totally unimodular matrix is enforced by filling up every row with ones between its first and its last non-zero entries. The resulting mistake is handled by introducing additional integer variables whose number depends on the reordering of the columns of the given matrix. This leads us to consider the consecutive block minimization problem. Two cutting plane algorithms are proposed and run on a large set of benchmark instances. The results obtained show that the cutting plane algorithms outperform an existing tree search method designed exclusively for such instances.