Abstract
In this paper we introduce and study the Knapsack Problem with Forfeits. With respect to the classical definition of the problem, we are given a collection of pairs of items, such that the inclusion of both in the solution involves a reduction of the profit. We propose a mathematical formulation and two heuristic algorithms for the problem. Computational results validate the effectiveness of our approaches.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Change history
22 July 2020
The original version of this chapter was revised. A typo in the second author’s family name was inadvertently introduced during the publication process. The family name has been corrected to “D’Ambrosio.”
References
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)
Carrabs, F., Cerrone, C., D’Ambrosio, C., Raiconi, A.: Column generation embedding carousel greedy for the maximum network lifetime problem with interference constraints. In: Sforza, A., Sterle, C. (eds.) ODS 2017. SPMS, vol. 217, pp. 151–159. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67308-0_16
Carrabs, F., Cerulli, R., D’Ambrosio, C., Raiconi, A.: Prolonging lifetime in wireless sensor networks with interference constraints. In: Au, M.H.A., Castiglione, A., Choo, K.-K.R., Palmieri, F., Li, K.-C. (eds.) GPC 2017. LNCS, vol. 10232, pp. 285–297. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57186-7_22
Carrabs, F., Cerulli, R., Pentangelo, R., Raiconi, A.: Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach. Ann. Oper. Res. 1–14 (2018). https://doi.org/10.1007/s10479-018-2895-y
Cerrone, C., Cerulli, R., Golden, B.: Carousel greedy: a generalized greedy algorithm with applications in optimization. Comput. Oper. Res. 85, 97–112 (2017)
Cerrone, C., D’Ambrosio, C., Raiconi, A.: Heuristics for the strong generalized minimum label spanning tree problem. Networks 74(2), 148–160 (2019)
Darmann, A., Pferschy, U., Schauer, J.: Minimal spanning trees with conflict graphs. Optimization online (2009)
Epstein, L., Levin, A.: On bin packing with conflicts. SIAM J. Optim. 19(3), 1270–1298 (2008)
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)
Gurski, F., Rehs, C.: The knapsack problem with conflict graphs and forcing graphs of bounded clique-width. In: Fortz, B., Labbé, M. (eds.) Operations Research Proceedings 2018. ORP, pp. 259–265. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-18500-8_33
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)
Hifi, M., Otmani, N.: An algorithm for the disjunctively constrained knapsack problem. Int. J. Oper. Res. 13(1), 22–43 (2012)
Kanté, M.M., Laforest, C., Momège, B.: Trees in graphs with conflict edges or forbidden transitions. In: Chan, T.-H.H., Lau, L.C., Trevisan, L. (eds.) TAMC 2013. LNCS, vol. 7876, pp. 343–354. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38236-9_31
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: Stat. Mech. Appl. 536 (2019). Article Number 122124
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)
Pferschy, U., Schauer, J.: The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13(2), 233–249 (2009)
Pferschy, U., Schauer, J.: The maximum flow problem with conflict and forcing conditions. In: Pahl, J., Reiners, T., Voß, S. (eds.) INOC 2011. LNCS, vol. 6701, pp. 289–294. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21527-8_34
Pferschy, U., Schauer, J.: Approximation of knapsack problems with conflict and forcing graphs. J. Comb. Optim. 33(4), 1300–1323 (2016). https://doi.org/10.1007/s10878-016-0035-7
Sadykov, R., Vanderbeck, F.: Bin packing with conflicts: a generic branch-and-price algorithm. INFORMS J. Comput. 25(2), 244–255 (2013)
Samer, P., Urrutia, S.: A branch and cut algorithm for minimum spanning trees under conflict constraints. Optim. Lett. 9(1), 41–55 (2014). https://doi.org/10.1007/s11590-014-0750-x
Zhang, R., Kabadi, S.N., Punnen, A.P.: The minimum spanning tree problem with conflict constraints and its variations. Discret. Optim. 8(2), 191–205 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Cerulli, R., D’Ambrosio, C., Raiconi, A., Vitale, G. (2020). The Knapsack Problem with Forfeits. In: Baïou, M., Gendron, B., Günlük, O., Mahjoub, A.R. (eds) Combinatorial Optimization. ISCO 2020. Lecture Notes in Computer Science(), vol 12176. Springer, Cham. https://doi.org/10.1007/978-3-030-53262-8_22
Download citation
DOI: https://doi.org/10.1007/978-3-030-53262-8_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-53261-1
Online ISBN: 978-3-030-53262-8
eBook Packages: Computer ScienceComputer Science (R0)