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

被引：4
|
作者：
Li, Ruizhi [1 ,2 ]
Wang, Yupan [3 ]
Hu, Shuli [3 ]
Jiang, Jianhua [1 ]
Ouyang, Dantong [2 ]
Yin, Minghao [3 ,4 ]
机构：
[1] Jilin Univ Finance & Econ, Sch Management Sci & Informat Engn, Changchun 130117, Peoples R China
[2] Jilin Univ, Sch Comp Sci & Technol, Changchun 130012, Peoples R China
[3] Northeast Normal Univ, Sch Comp Sci & Informat Technol, Changchun 130024, Peoples R China
[4] Northeast Normal Univ, MOE, Key Lab Appl Stat, Changchun 130117, Peoples R China
来源：
MATHEMATICAL PROBLEMS IN ENGINEERING | 2020年 / 2020卷
基金：
中国国家自然科学基金; 中国博士后科学基金;
关键词：
EFFICIENT LOCAL SEARCH; CONFIGURATION CHECKING; GENETIC ALGORITHM; GRASP;
D O I：
10.1155/2020/3050714
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
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.
引用
收藏
页数：11
相关论文
共 50 条
  • [31] Algorithm of Solving the Maximum Edges Independent Set Problem Based on DNA Molecules Computation
    Wang, Zhaocai
    Huang, Wei
    Ye, Chaorong
    Zhang, Yiming
    JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2014, 11 (04) : 961 - 963
  • [32] O(20.304N ) ALGORITHM FOR SOLVING MAXIMUM INDEPENDENT SET PROBLEM.
    Jian, Tang
    IEEE Transactions on Computers, 1986, C-35 (09) : 847 - 851
  • [33] Sticker model for maximum clique problem and maximum independent set
    Fan Y.-K.
    Qiang X.-L.
    Xu J.
    Jisuanji Xuebao/Chinese Journal of Computers, 2010, 33 (02): : 305 - 310
  • [34] On the Maximum Independent Set Problem in Graphs of Bounded Maximum Degree
    Le, Ngoc C.
    Trung Tran
    ACTA MATHEMATICA VIETNAMICA, 2020, 45 (02) : 463 - 475
  • [35] On the Maximum Independent Set Problem in Graphs of Bounded Maximum Degree
    Ngoc C. Lê
    Trung Tran
    Acta Mathematica Vietnamica, 2020, 45 : 463 - 475
  • [36] An augmentation algorithm for the maximum weighted stable set problem
    Mannino, C
    Stefanutti, E
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 1999, 14 (03) : 367 - 381
  • [37] An Augmentation Algorithm for the Maximum Weighted Stable Set Problem
    Carlo Mannino
    Egidio Stefanutti
    Computational Optimization and Applications, 1999, 14 : 367 - 381
  • [38] A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithm
    Oztemiz, Furkan
    ENGINEERING SCIENCE AND TECHNOLOGY-AN INTERNATIONAL JOURNAL-JESTECH, 2025, 63
  • [39] Large Neighborhood Local Search for the Maximum Set Packing Problem
    Sviridenko, Maxim
    Ward, Justin
    AUTOMATA, LANGUAGES, AND PROGRAMMING, PT I, 2013, 7965 : 792 - 803
  • [40] A GENETIC ALGORITHM FOR THE MAXIMUM 2-PACKING SET PROBLEM
    Antonio Trejo-Sanchez, Joel
    Fajardo-Delgado, Daniel
    Octavio Gutierrez-Garcia, J.
    INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE, 2020, 30 (01) : 173 - 184
12345