A framework to exploit the structure of and solve set packing problems with a semi-block-angular structure. (November 2019)

• Record Type: Journal Article
• Authors: Radman, Maryam; Eshghi, Kourosh
• Is Part Of: Computers & industrial engineering. Volume 137(2019)
• Publication Date: 2019-11
• Subjects: Set packing problem -- Semi-block-angular structure -- Constraint partitioning -- Decomposition technique; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.106036
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A novel method is proposed to solve set packing problems (SPPs). The proposed method is a decomposition algorithm based on constraint partitioning. The proposed method exploits special structures of SPPs using clustering methods. The method solves the problem through solving the subproblems of the structures. A theorem is developed to relate the optimal value of SPPs to its sub-problems. Abstract: Real-world, large-scale problems often have coefficient matrices with special structures that can be obtained by reordering their rows and columns. One fundamental problem in the field of combinatorial optimization is the Set Packing Problem (SPP), which takes on added significance in view of its far-reaching applications in routing and scheduling problems, scheduling surgical procedures, the winner determination problem, forestry, production management, etc. The coefficient matrix of this problem has low density (the number of 1's is much less than the number of 0's in the matrix); therefore, by reordering the matrix, one can aggregate its 1's in order to exploit special structures like semi-block-angular ones. In this paper, a decomposition technique based on constraint partitioning is proposed for exploiting the semi-block-angular structures of SPPs and solving the original problem through solving the sub-problems of the obtained structure. In addition, a theorem is developed to relate the optimal values of the original problem to its sub-problems. The results of implementing the proposed algorithm on some sample test problems demonstrate the ability of the algorithm to exploit semi-block-angular structures and achieve optimal solutions for SPPs. In addition, the application of the proposed algorithm to solve SPPs without a semi-block-angular structure is also investigated on some test problems of OR-library.