A Nested Decomposition Approach for a Large Scale Set Covering Problem: A Model with a Variety of Applications in Industry 4.0

Maryam Radman () and Kourosh Eshghi ()
Additional contact information
Maryam Radman: Sharif University of Technology
Kourosh Eshghi: Sharif University of Technology

A chapter in Optimization in Large Scale Problems, 2019, pp 165-177 from Springer

Abstract: Abstract This chapter at first proposes a framework to solve set covering problems (SCPs) with block-angular structures through solving their sub-problems and then develop the method for solving general SCPs without this structure. The proposed framework generates a guaranteed solution for the SCPs with block-angular structure based on a theorem which relates the optimal solution of the original problem to the optimal solutions of its sub-problems. Therefore, since sub-problems involve much fewer constraints and variables than the original problem, the complexity to solve the original SCP is much reduced. In addition, a method to exploit the block-angular structure of SCPs is proposed, using constraint partitioning. The partitioning is based on the fact that the coefficient matrix of SCPs has low density (the number of 1’s is much less than the number of 0’s in the coefficient matrix), so by reordering the rows and the columns, block-angular structures can be created. Our experimental results demonstrate the ability of the proposed approach to exploit the block-angular structures and achieve optimal solutions on sample test problems. In addition, the development of the proposed method to solve SCPs without this structure is examined on benchmark instances of OR-Library.

Keywords: Set covering; Block-angular; Constraint partitioning; Decomposition techniques (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-030-28565-4_17

Ordering information: This item can be ordered from
http://www.springer.com/9783030285654

DOI: 10.1007/978-3-030-28565-4_17

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().