Solving the set packing problem via a maximum weighted independent set heuristic
type: Item
instance of: scholarly article
title: Solving the set packing problem via a maximum weighted independent set heuristic
zbMATH Open document ID: 1459.90186
DOI: 10.1155/2020/3050714
author: Ruizhi Li
author: Yupan Wang
author: Shuli Hu
author: Jianhua Jiang
author: Dantong Ouyang
author: Minghao Yin
published in: Mathematical Problems in Engineering
publication date: 2021-01-04T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7290051
describes a project that uses: CCASat
describes a project that uses: SCCWalk
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2020/3050714
OpenAlex ID: W3111113712
cites work: Routing trains through a railway station based on a node packing model
cites work: Combinatorial auctions: a survey
cites work: Q3416578
cites work: Online Set Packing
cites work: Q4198056
cites work: On the facial structure of set packing polyhedra
cites work: New facets for the set packing polytope
cites work: Facet Obtaining Procedures for Set Packing Problems
cites work: A set packing model for the ground holding problem in congested networks
cites work: On a posterior evaluation of a simple greedy method for set packing
cites work: Alternative formulations for the set packing problem and their application to the winner determination problem
cites work: A biased random-key genetic algorithm for the minimization of open stacks problem
cites work: Hybridizations of GRASP with path relinking for the far from most string problem
cites work: A biased random-key genetic algorithm for single-round divisible load scheduling
cites work: SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem
cites work: A method for the cutting stock problem with different qualities
cites work: Greedy local improvement and weighted set packing approximation
cites work: GRASP for set packing problems.
cites work: Heuristics for a bidding problem
cites work: A new approach for modeling and solving set packing problems
cites work: Large Neighborhood Local Search for the Maximum Set Packing Problem
cites work: A hybrid evolutionary approach for set packing problem
cites work: An evolutionary algorithm based hyper-heuristic framework for the set packing problem
cites work: An efficient local search framework for the minimum weighted vertex cover problem
cites work: Local search with edge weighting and configuration checking heuristics for minimum vertex cover
cites work: Local search for Boolean satisfiability with configuration checking and subscore
cites work: Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
description: scientific article; zbMATH DE number 7290051