Solving the Set Packing Problem via a Maximum Weighted Independent Set Heuristic

Ruizhi Li, Yupan Wang, Shuli Hu, Jianhua Jiang, Dantong Ouyang and Minghao Yin

Mathematical Problems in Engineering, 2020, vol. 2020, 1-11

Abstract:

The set packing problem (SPP) is a significant NP-hard combinatorial optimization problem with extensive applications. In this paper, we encode the set packing problem as the maximum weighted independent set (MWIS) problem and solve the encoded problem with an efficient algorithm designed to the MWIS problem. We compare the independent set-based method with the state-of-the-art algorithms for the set packing problem on the 64 standard benchmark instances. The experimental results show that the independent set-based method is superior to the existing algorithms in terms of the quality of the solutions and running time obtained the solutions.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2020/3050714.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2020/3050714.xml (text/xml)

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:hin:jnlmpe:3050714

DOI: 10.1155/2020/3050714

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().