The knapsack problem with forfeit sets. (English) Zbl 1542.90197
Summary: This work introduces a novel extension of the 0/1 Knapsack Problem in which we consider the existence of so-called forfeit sets. A forfeit set is a subset of items of arbitrary cardinality, such that including a number of its elements that exceeds a predefined allowance threshold implies some penalty costs to be paid in the objective function value. A global upper bound on these allowance violations is also considered. We show that the problem generalizes both the Knapsack Problem with conflicts among item pairs and the Knapsack Problem with forfeit pairs, that have been previously introduced in the literature. We present a polynomial subcase by proving the integrality of its LP relaxation polytope and, we introduce three heuristic approaches, namely a constructive greedy, an algorithm based on the recently introduced Carousel Greedy paradigm and a hybrid Memetic/Carousel Greedy algorithm. Finally, we validate the performances for the proposed algorithms on a set of benchmark instances that consider both random and correlated data.
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
knapsack problem; conflicts; forfeit sets; carousel greedy; memetic algorithm; hybrid metaheuristicReferences:
| [1] | Akinc, U., Approximate and exact algorithms for the fixed-charge Knapsack problem, European J. Oper. Res., 170, 363-375 (2006) · Zbl 1085.90049 |
| [2] | Basnet, C., Heuristics for the multiple Knapsack problem with conflicts, Int. J. Oper. Res., 32, 4, 514-525 (2018) |
| [3] | Ben Salem, M.; Taktak, R.; Mahjoub, A. R.; Ben-Abdallah, H., Optimization algorithms for the disjunctively constrained Knapsack problem, Soft Comput., 22, 2025-2043 (2018) · Zbl 1398.90131 |
| [4] | Bettinelli, A.; Cacchiani, V.; Malaguti, E., A branch-and-bound algorithm for the Knapsack problem with conflict graph, INFORMS J. Comput., 29, 3, 457-473 (2017) · Zbl 1386.90123 |
| [5] | Cacchiani, V.; Iori, M.; Locatelli, A.; Martello, S., Knapsack problems — An overview of recent advances. Part I: Single Knapsack problems, Comput. Oper. Res., 143, Article 105692 pp. (2022) · Zbl 1512.90189 |
| [6] | Cacchiani, V.; Iori, M.; Locatelli, A.; Martello, S., Knapsack problems — An overview of recent advances. Part II: Multiple, multidimensional, and quadratic Knapsack problems, Comput. Oper. Res., 143, Article 105693 pp. (2022) · Zbl 1512.90190 |
| [7] | Capobianco, G.; D’Ambrosio, C.; Pavone, L.; Raiconi, A.; Vitale, G.; Sebastiano, F., A hybrid metaheuristic for the Knapsack problem with forfeits, Soft Comput., 26, 749-762 (2022) |
| [8] | Carrabs, F., Cerrone, C., D’Ambrosio, C., Raiconi, A., 2017. Column Generation Embedding Carousel Greedy for the Maximum Network Lifetime Problem with Interference Constraints. In: Springer Proceedings in Mathematics and Statistics, Vol. 217. pp. 151-159. |
| [9] | Carrabs, F.; Cerulli, R.; Pentangelo, R.; Raiconi, A., Minimum spanning tree with conflicting edge pairs: A branch-and-cut approach, Ann. Oper. Res., 298, 65-78 (2021) · Zbl 1514.90233 |
| [10] | Cerrone, C.; Cerulli, R.; Gaudioso, M., OMEGA one multi ethnic genetic approach, Optim. Lett., 10, 2, 309-324 (2016) · Zbl 1343.90105 |
| [11] | Cerrone, C.; Cerulli, R.; Golden, B., Carousel greedy: A generalized greedy algorithm with applications in optimization, Comput. Oper. Res., 85, 97-112 (2017) · Zbl 1458.90643 |
| [12] | Cerrone, C.; D’Ambrosio, C.; Raiconi, A., Heuristics for the strong generalized minimum label spanning tree problem, Networks, 74, 2, 148-160 (2019) |
| [13] | Cerrone, C.; Gentili, M.; D’Ambrosio, C.; Cerulli, R., An efficient and simple approach to solve a distribution problem, (AIRO Springer Series, vol. 1 (2018)), 151-159 |
| [14] | Cerulli, R.; D’Ambrosio, C.; Iossa, A.; Palmieri, F., Maximum network lifetime problem with time slots and coverage constraints: Heuristic approaches, J. Supercomput., 78, 1, 1330-1355 (2022) |
| [15] | Cerulli, R.; D’Ambrosio, C.; Raiconi, A.; Vitale, G., The Knapsack problem with forfeits, (Combinatorial Optimization. 5th International Symposium. Combinatorial Optimization. 5th International Symposium, ISCO 2020. Combinatorial Optimization. 5th International Symposium. Combinatorial Optimization. 5th International Symposium, ISCO 2020, Lecture Notes in Computer Science, vol. 12176 (2020)), 263-272 · Zbl 1458.90540 |
| [16] | Ceselli, A.; Righini, G., An optimization algorithm for a penalized Knapsack problem, Oper. Res. Lett., 34, 394-404 (2006) · Zbl 1133.90383 |
| [17] | Coniglio, S.; Furini, F.; San Segundo, P., A new combinatorial branch-and-bound algorithm for the Knapsack problem with conflicts, European J. Oper. Res., 289, 2, 435-455 (2021) · Zbl 1487.90546 |
| [18] | Dahmani, I.; Hifi, M., A modified descent method-based heuristic for binary quadratic Knapsack problems with conflict graphs, Ann. Oper. Res., 298, 125-147 (2021) · Zbl 1467.90050 |
| [19] | Darmann, A.; Pferschy, U.; Schauer, J., Determining a minimum spanning tree with disjunctive constraints, (Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5783 LNAI (2009)), 414-423 · Zbl 1260.68171 |
| [20] | Darmann, A.; Pferschy, U.; Schauer, J.; Woeginger, G., Paths, trees and matchings under disjunctive constraints, Discrete Appl. Math., 159, 16, 1726-1735 (2011) · Zbl 1228.05186 |
| [21] | Della Croce, F.; Pferschy, U.; Scatamacchia, R., New exact approaches and approximation results for the Penalized Knapsack problem, Discrete Appl. Math., 253, 122-135 (2019) · Zbl 1411.90292 |
| [22] | Eiben, A. E.; Smith, J. E., (Introduction to Evolutionary Computing. Introduction to Evolutionary Computing, Natural Computing Series (2015), Springer-Verlag Berlin Heidelberg: Springer-Verlag Berlin Heidelberg Berlin, Heidelberg) · Zbl 1327.68003 |
| [23] | Epstein, L.; Levin, A., On bin packing with conflicts, SIAM J. Optim., 19, 3, 1270-1298 (2008) · Zbl 1175.68200 |
| [24] | Gendreau, M.; Laporte, G.; Semet, F., Heuristics and lower bounds for the bin packing problem with conflicts, Comput. Oper. Res., 31, 3, 347-358 (2004) · Zbl 1107.90033 |
| [25] | Goldschmidt, O.; Nehme, D.; Yu, G., Note: On the set-union Knapsack problem, Nav. Res. Logist., 41, 833-842 (1994) · Zbl 0831.90088 |
| [26] | Hadi, K.; Lasri, R.; El Abderrahmani, A., An efficient approach for sentiment analysis in a big data environment, Int. J. Eng. Adv. Technol., 8, 4, 263-266 (2019) |
| [27] | He, Y.; Xie, H.; Wong, T.-L.; Wang, X., A novel binary artificial bee colony algorithm for the set-union Knapsack problem, Future Gener. Comput. Syst., 78, 77-86 (2018) |
| [28] | Heller, I.; Tompkins, C., An extension of a theorem of Dantzig’s, (Linear Inequalities and Related Systems, Vol. 38 (1956), Princeton University Press: Princeton University Press Princeton), 247-254 · Zbl 0072.37804 |
| [29] | Hifi, M.; Otmani, N., An algorithm for the disjunctively constrained Knapsack problem, Int. J. Oper. Res., 13, 1, 22-43 (2012) · Zbl 1362.90370 |
| [30] | Kong, H.; Kang, Q.; Li, W.; Liu, C.; Kang, Y.; He, H., A hybrid iterated carousel greedy algorithm for community detection in complex networks, Physica A, 536, Article 122124 pp. (2019) |
| [31] | Luiz, T. A.; Santos, H. G.; Uchoa, E., Cover by disjoint cliques cuts for the Knapsack problem with conflicting items, Oper. Res. Lett., 49, 6, 844-850 (2021) · Zbl 1525.90367 |
| [32] | Muritiba, A. E.F.; Iori, M.; Malaguti, E.; Toth, P., Algorithms for the bin packing problem with conflicts, INFORMS J. Comput., 22, 3, 401-415 (2010) · Zbl 1243.90189 |
| [33] | Pferschy, U.; Schauer, J., The Knapsack problem with conflict graphs, J. Graph Algorithms Appl., 13, 2, 233-249 (2009) · Zbl 1194.68175 |
| [34] | Pferschy, U.; Schauer, J., The maximum flow problem with conflict and forcing conditions, (International Conference on Network Optimization (2011), Springer), 289-294 · Zbl 1345.05040 |
| [35] | Pferschy, U.; Schauer, J., Approximation of Knapsack problems with conflict and forcing graphs, J. Comb. Optim., 33, 4, 1300-1323 (2017) · Zbl 1376.90052 |
| [36] | Sadykov, R.; Vanderbeck, F., Bin packing with conflicts: A generic branch-and-price algorithm, INFORMS J. Comput., 25, 2, 244-255 (2013) |
| [37] | Samer, P.; Urrutia, S., A branch and cut algorithm for minimum spanning trees under conflict constraints, Optim. Lett., 9, 1, 41-55 (2015) · Zbl 1308.90033 |
| [38] | Shi, X.; Wu, L.; Meng, X., A new optimization model for the sustainable development: Quadratic Knapsack problem with conflict graphs, Sustainability, 9, 2, 236 (2017) |
| [39] | Stefanov, S. M., Separable Programming: Theory and Methods (2013), Springer New York: Springer New York New York |
| [40] | Wu, C.; He, Y., Solving the set-union Knapsack problem by a novel hybrid Jaya algorithm, Soft Comput., 24, 3, 1883-1902 (2020) |
| [41] | Yamada, T.; Takeoka, T., An exact algorithm for the fixed-charge multiple Knapsack problem, European J. Oper. Res., 192, 700-705 (2009) · Zbl 1157.90485 |
| [42] | Zhang, R.; Kabadi, S. N.; Punnen, A. P., The minimum spanning tree problem with conflict constraints and its variations, Discrete Optim., 8, 2, 191-205 (2011) · Zbl 1241.90167 |
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.
