×

Solving the set packing problem via a maximum weighted independent set heuristic. (English) Zbl 1459.90186

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.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Software:

CCASat; SCCWalk
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Peter, J. Z.; Leo, G. K.; Stan, P. V., Routing trains through a railway station based on a node packing model, European Journal of Operational Research, 128, 1, 14-33 (2001) · Zbl 0982.90004
[2] Sven, D. V.; Rakesh, V. V., Combinatorial auctions: a survey, Informs Journal on Computing, 15, 3, 284-309 (2003) · Zbl 1238.91003
[3] Vela´squez, R.; Melo, M. T., A set packing approach for scheduling elective surgical procedures, Operations Research Proceedings, 425-430 (2006), Berlin, Germany: Springer, Berlin, Germany · Zbl 1114.90393
[4] Yuval, E.; Magnu´s, M. H.; Yishay, M.; Boaz, P. S.; Jaikumar, R.; Dror, R., Online set packing, SIAM Journal on Computing, 41, 4, 728-746 (2012) · Zbl 1286.68488
[5] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), San Francisco, CA, USA: W.H. Freeman and Company, San Francisco, CA, USA · Zbl 0411.68039
[6] Padberg, M. W., On the facial structure of set packing polyhedra, Mathematical Programming, 5, 1, 199-215 (1973) · Zbl 0272.90041 · doi:10.1007/bf01580121
[7] Cánovas, L.; Landete, M.; Marı́n, A., New facets for the set packing polytope, Operations Research Letters, 27, 4, 153-161 (2000) · Zbl 1096.90548 · doi:10.1016/s0167-6377(00)00056-0
[8] Cánovas, L.; Landete, M.; Marín, A., Facet obtaining procedures for set packing problems, SIAM Journal Discrete Math, 16, 127-155 (2003) · Zbl 1029.05131
[9] Rossi, F.; Smriglio, S., A set packing model for the ground holding problem in congested networks, European Journal of Operational Research, 131, 2, 400-416 (2001) · Zbl 0991.90021 · doi:10.1016/s0377-2217(00)00064-3
[10] Kwon, R. H.; Dalakouras, G. V.; Wang, C., On a posterior evaluation of a simple greedy method for set packing, Optimization Letters, 2, 4, 587-597 (2008) · Zbl 1177.90296 · doi:10.1007/s11590-008-0085-6
[11] Kolokolov, A. A.; Zaozerskaya, L. A., On average number of iterations of some algorithms for solving the set packing problem, IFAC Proceedings Volumes, 42, 4, 1510-1513 (2009) · doi:10.3182/20090603-3-ru-2001.0519
[12] Landete, M.; Rodríguez-Chía, A. M.; Antonio, M.; Rodríguez-Chía, Alternative formulations for the set packing problem and their application to the winner determination problem, Annals of Operations Research, 207, 1, 137-160 (2013) · Zbl 1297.90138 · doi:10.1007/s10479-011-1039-4
[13] Li, R.; Hu, S.; Wang, Y.; Yin, M., A local search algorithm with tabu strategy and perturbation mechanism for generalized vertex cover problem, Neural Computing and Applications, 28, 7, 1775-1785 (2017) · doi:10.1007/s00521-015-2172-9
[14] Li, R. Z.; Hu, S. L.; Gao, J.; Zhou, Y. P.; Wang, Y. Y.; Yin, M. H., GRASP for connected dominating set problems, Neural Computing and Applications, 28, 1, 1059-1067 (2017) · doi:10.1007/s00521-016-2429-y
[15] Gonçalves, J. F.; Resende, M. G. C.; Costa, M. D., A biased random-key genetic algorithm for the minimization of open stacks problem, International Transactions in Operational Research, 23, 1-2, 25-46 (2016) · Zbl 1338.90338 · doi:10.1111/itor.12109
[16] Ferone, D.; Festa, P.; Resende, M. G. C., Hybridizations of GRASP with path relinking for the far from most string problem, International Transactions in Operational Research, 23, 3, 481-506 (2016) · Zbl 1342.90161 · doi:10.1111/itor.12167
[17] Brandão, J. S.; Noronha, T. F.; Resende, M. G. C.; Ribeiro, C. C., A biased random-key genetic algorithm for single-round divisible load scheduling, International Transactions in Operational Research, 22, 5, 823-839 (2015) · Zbl 1338.90160 · doi:10.1111/itor.12178
[18] Wang, Y.; Cai, S.; Chen, J.; Yin, M., SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem, Artificial Intelligence, 280, 103230 (2020) · Zbl 1476.68218 · doi:10.1016/j.artint.2019.103230
[19] Wang, Y.; Li, C.; Yin, M., A two phase removing algorithm for minimum independent dominating set problem, Applied Soft Computing, 88, 105949 (2020) · doi:10.1016/j.asoc.2019.105949
[20] Zhang, X.; Li, X. T.; Yin, M. H., An enhanced genetic algorithm for the distributed assembly permutation flowshop scheduling problem, International Journal of Bio-Inspired Computation, 15, 2, 113-124 (2020) · doi:10.1504/ijbic.2020.10028014
[21] Zhou, Y.; Qiu, C.; Wang, Y.; Fan, M.; Yin, M., An improved memetic algorithm for the partial vertex cover problem, IEEE Access, 7, 17389-17402 (2019) · doi:10.1109/access.2019.2895738
[22] Zhang, X.; Li, X. T.; Wang, J. N., Local search algorithm with path relinking for single batch-processing machine scheduling problem, Neural Computing and Applications, 28, 1, 313-326 (2017) · doi:10.1007/s00521-016-2339-z
[23] Rönnqvist, M., A method for the cutting stock problem with different qualities, European Journal of Operational Research, 83, 1, 57-68 (1995) · Zbl 0903.90136 · doi:10.1016/0377-2217(94)00023-6
[24] Chandra, B.; Halldórsson, M. M., Greedy local improvement and weighted set packing approximation, Journal of Algorithms, 39, 2, 223-240 (2001) · Zbl 0974.68238 · doi:10.1006/jagm.2000.1155
[25] Lau, H. C.; Goh, Y. G., An intelligent brokering system to support multi-agent Web-based 4/sup th/-party logistics, Proceedings 14th IEEE International Conference on Tools with Artificial Intelligence, 2002 (ICTAI 2002)
[26] Delorme, X.; Gandibleux, X.; Rodriguez, J., GRASP for set packing problems, European Journal of Operational Research, 153, 3, 564-580 (2004) · Zbl 1099.90572 · doi:10.1016/s0377-2217(03)00263-7
[27] Gandibleux, X.; Delorme, X.; T’Kindt, V., An Ant Colony Optimisation Algorithm for the Set Packing Problem, 49-60 (2004), Berlin, Germany: Springer-Verlag, Berlin, Germany
[28] Guo, Y.; Lim, A.; Rodrigues, B.; Zhu, Y., Heuristics for a bidding problem, Computers & Operations Research, 33, 8, 2179-2188 (2006) · Zbl 1086.90062 · doi:10.1016/j.cor.2005.01.007
[29] Alidaee, B.; Kochenberger, G.; Lewis, K.; Lewis, M.; Wang, H., A new approach for modeling and solving set packing problems, European Journal of Operational Research, 186, 2, 504-512 (2008) · Zbl 1146.90479 · doi:10.1016/j.ejor.2006.12.068
[30] Gandibleux, X.; Jorge, J.; Delorme, X.; Rodriguez, J.; Monmarche´, N.; Guinand, F.; Siarry, P., An Ant Algorithm for Measuring and Optimizing the Capacity of a Railway Infrastructure (2010), Hoboken, NJ, USA: ISTE Ltd and John Wiley, Hoboken, NJ, USA
[31] Merel, A.; Gandibleux, X.; Demassey, S., A collaborative combination between column generation and ant colony optimization for solving set packing problems, Proceedings of the The IX Metaheuristics International Conference
[32] Sviridenko, M.; Ward, J., Large neighborhood local search for the maximum set packing problem, International Colloquium on Automata, Languages, and Programming, 792-803 (2013), Berlin, Germany: Springer, Berlin, Germany · Zbl 1336.68241
[33] Chaurasia, S. N.; Sundar, S.; Singh, A., A hybrid evolutionary approach for set packing problem, OPSEARCH, 52, 2, 271-284 (2015) · Zbl 1332.90223 · doi:10.1007/s12597-014-0184-3
[34] Chaurasia, S. N.; Jung, D.; Lee, H. M.; Kim, J. H.; Yadav, N.; Yadav, A.; Bansal, J.; Deep, K.; Kim, J., An evolutionary algorithm based hyper-heuristic for the set packing problem, Harmony Search and Nature Inspired Optimization Algorithms. Advances in Intelligent Systems and Computing (2019), Berlin, Germany: Springer, Berlin, Germany
[35] Chaurasia, S. N.; Kim, J. H., An evolutionary algorithm based hyper-heuristic framework for the set packing problem, Information Sciences, 505, 12, 1-31 (2019) · Zbl 1456.90177 · doi:10.1016/j.ins.2019.07.073
[36] Radman, M.; Eshghi, K., A framework to exploit the structure of and solve set packing problems with a semi-block-angular structure, Computers & Industrial Engineering, 137, Nov., 106036.113-106036.1061 (2019) · doi:10.1016/j.cie.2019.106036
[37] Li, R.; Hu, S.; Zhang, H.; Yin, M., An efficient local search framework for the minimum weighted vertex cover problem, Information Sciences, 372, 428-445 (2016) · Zbl 1428.90183 · doi:10.1016/j.ins.2016.08.053
[38] Cai, S.; Su, K.; Sattar, A., Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Artificial Intelligence, 175, 9-10, 1672-1696 (2011) · Zbl 1225.68242 · doi:10.1016/j.artint.2011.03.003
[39] Wang, Y. Y.; Ouyang, D. T.; Zhang, L. M.; Yin, M. H., A novel local search for unicast set covering problem using hyperedge configuration checking and weight diversity, SCIENCE CHINA Information Science, 60, 6 (2017) · doi:10.1007/s11432-015-5377-8
[40] Luo, C.; Cai, S. W.; Su, K. L.; Wu, W., Clause states based configuration checking in local search for satisfiability, Cybernetics, IEEE Transactions on., 45, 5, 1014-1027 (2015)
[41] Cai, S.; Su, K., Local search for Boolean Satisfiability with configuration checking and subscore, Artificial Intelligence, 204, 75-98 (2013) · Zbl 1334.68200 · doi:10.1016/j.artint.2013.09.001
[42] Wang, Y.; Cai, S.; Yin, M., Local search for minimum weight dominating set with two-level configuration checking and frequency based scoring function, Journal of Artificial Intelligence Research, 58, 267-295 (2017) · Zbl 1404.68146 · doi:10.1613/jair.5205
[43] Li, R.; Hu, P. S.; YinZhou, M. Y., A novel local search algorithm for the minimum capacitated dominating set, Journal of the Operational Research Society, 69, 6, 849-863 (2018) · doi:10.1057/s41274-017-0268-6
[44] Hu, S.; Li, R.; Zhao, P.; Yin, M., A hybrid metaheuristic algorithm for generalized vertex cover problem, Memetic Computing, 10, 2, 165-176 (2018) · doi:10.1007/s12293-016-0216-z
[45] Alidaee, B.; Wang, H., A note on heuristic approach based on UBQP formulation of the maximum diversity problem, Journal of the Operational Research Society, 68, 1, 102-110 (2017) · doi:10.1057/s41274-016-0031-4
[46] Li, R.; Wu, X.; Liu, H.; Wu, J.; Yin, M., An efficient local search for the maximum edge weighted clique problem, IEEE Access, 6, 10743-10753 (2018) · doi:10.1109/access.2018.2799953
[47] Zhou, Y.; Wang, J.; Wu, Z.; Wu, K., A multi-objective tabu search algorithm based on decomposition for multi-objective unconstrained binary quadratic programming problem, Knowledge-Based Systems, 141, 2, 18-30 (2018) · doi:10.1016/j.knosys.2017.11.009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.