{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T12:02:40Z","timestamp":1772712160265,"version":"3.50.1"},"reference-count":49,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2024,5,18]],"date-time":"2024-05-18T00:00:00Z","timestamp":1715990400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSERC"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this paper, we study the knapsack problem with conflict pair constraints. After a thorough literature survey on the topic, our study focuses on the special case of bipartite conflict graphs. For complete bipartite (multipartite) conflict graphs, the problem is shown to be NP-hard but solvable in pseudo-polynomial time, and it admits an FPTAS. Extensions of these results to more general classes of graphs are also presented. Further, a class of integer programming models for the general knapsack problem with conflict pair constraints is presented, which generalizes and unifies the existing formulations. The strength of the LP relaxations of these formulations is analyzed, and we discuss different ways to tighten them. Experimental comparisons of these models are also presented to assess their relative strengths. This analysis disclosed various strong and weak points of different formulations of the problem and their relationships to different types of problem data. This information can be used in designing special purpose algorithms for KPCC involving a learning component.<\/jats:p>","DOI":"10.3390\/a17050219","type":"journal-article","created":{"date-parts":[[2024,5,20]],"date-time":"2024-05-20T03:36:42Z","timestamp":1716176202000},"page":"219","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions"],"prefix":"10.3390","volume":"17","author":[{"given":"Abraham P.","family":"Punnen","sequence":"first","affiliation":[{"name":"Department of Mathematics, Simon Fraser University, Surrey, BC V5A 1S6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jasdeep","family":"Dhahan","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Simon Fraser University, Surrey, BC V5A 1S6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,5,18]]},"reference":[{"key":"ref_1","unstructured":"Bandyapadhyay, S. (2014). A variant of the maximum weight independent set problem. arXiv."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1007\/978-3-319-53007-9_23","article-title":"Maximum weighted independent with a budget","volume":"Volume 10156","author":"Gaur","year":"2017","journal-title":"Proceedings of the Algorithms and Discrete Applied Mathematics: Third International Conference, CALDAM 2017"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/j.endm.2009.11.052","article-title":"The exact weighted independent set problem in perfect graphs and related classes","volume":"35","author":"Milanic","year":"2009","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1016\/j.cie.2011.01.019","article-title":"Local branching-based algorithms for the disjunctively constrained knapsack problem","volume":"60","author":"Akeb","year":"2011","journal-title":"Comput. Ind. Eng."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1057\/palgrave.jors.2602046","article-title":"A reactive local search algorithm for the disjunctively constrained knapsack problem","volume":"57","author":"Hifi","year":"2006","journal-title":"J. Oper. Res. Soc."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2657","DOI":"10.1016\/j.cor.2005.10.004","article-title":"Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem","volume":"34","author":"Hifi","year":"2007","journal-title":"Comput. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1504\/IJOR.2012.044026","article-title":"An algorithm for the disjunctively constrained knapsack problem","volume":"13","author":"Hifi","year":"2012","journal-title":"Int. J. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1068969","DOI":"10.1080\/23311916.2015.1068969","article-title":"A hybrid guided neighborhood search for the disjunctively constrained knapsack problem","volume":"2","author":"Hifi","year":"2015","journal-title":"Cogent Eng."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1109","DOI":"10.1080\/0305215X.2013.819096","article-title":"An iterative rounding search-based algorithm for the disjunctively constrained knapsack problem","volume":"46","author":"Hifi","year":"2014","journal-title":"Eng. Optim."},{"key":"ref_10","first-page":"2864","article-title":"Heuristic and exact algorithms for the disjunctively constrained knapsack problem","volume":"43","author":"Yamada","year":"2002","journal-title":"Inf. Process Soc. Jpn. J."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1002\/net.21883","article-title":"A multiethnic genetic approach for the minimum conflict weighted spanning tree problem","volume":"74","author":"Carrabs","year":"2019","journal-title":"Networks"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s10479-018-2895-y","article-title":"Minimum spanning tree with conflicting edge pairs: A branch-and-cut approach","volume":"298","author":"Carrabs","year":"2021","journal-title":"Ann. Oper. Res."},{"key":"ref_13","unstructured":"Darmann, A., Pferschy, U., and Schauer, J. (2009). Lecture Notes in Computer Science, Springer."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1726","DOI":"10.1016\/j.dam.2010.12.016","article-title":"Paths, trees and matchings under disjunctive constraints","volume":"159","author":"Darmann","year":"2011","journal-title":"Discret. Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1287\/ijoc.1100.0406","article-title":"A branch-and-price algorithm for the bin packing problem with conflicts","volume":"23","author":"Elhedhli","year":"2011","journal-title":"INFORMS J. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/S0305-0548(02)00195-8","article-title":"Heuristics and lower bounds for the bin packing problem with conflicts","volume":"31","author":"Gendreau","year":"2004","journal-title":"Comput. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1016\/j.cor.2012.10.022","article-title":"The minimum cost perfect matching problem with conflict pair constraints","volume":"40","author":"Oncan","year":"2013","journal-title":"Comput. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10878-011-9438-7","article-title":"The maximum flow problem with disjunctive constraints","volume":"26","author":"Pferschy","year":"2013","journal-title":"J. Comb. Optim."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.disopt.2010.08.001","article-title":"The minimum spanning tree problem with conflict constraints and its variations","volume":"8","author":"Zhang","year":"2011","journal-title":"Discret. Optim."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s11590-014-0750-x","article-title":"A branch and cut algorithm for minimum spanning trees under conflict constraints","volume":"9","author":"Samer","year":"2014","journal-title":"Optim. Lett."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/ijoc.1060.0181","article-title":"Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem","volume":"19","author":"Pisinger","year":"2007","journal-title":"INFORMS J. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1287\/ijoc.1120.0499","article-title":"Bin packing with conflicts: A generic branch-and-price algorithm","volume":"25","author":"Sadykov","year":"2013","journal-title":"INFORMS J. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1287\/ijoc.1090.0355","article-title":"Algorithms for the bin packing problem with conflicts","volume":"22","author":"Iori","year":"2010","journal-title":"INFORMS J. Comput."},{"key":"ref_24","unstructured":"Chandra, A.K., Hirschberg, D.S., and Wong, C.K. (1975). IBM Research Report, IBM T. J. Watson Research Center. RC56l6."},{"key":"ref_25","unstructured":"Nauss, R.M. (1975). The 0-1 Knapsack Problem with Multiple Choice Constraints, University of Missouri-St. Louis. (Revised in 1976)."},{"key":"ref_26","first-page":"59","article-title":"The multiple choice knapsack problem","volume":"21","author":"Ibaraki","year":"1978","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1145\/502102.502107","article-title":"A unified approach to approximating resource allocation and scheduling","volume":"48","author":"Freund","year":"2001","journal-title":"J. ACM"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1287\/ijoc.2016.0742","article-title":"A branch-and-bound algorithm for the knapsack problem with conflict graph","volume":"29","author":"Bettinelli","year":"2017","journal-title":"INFORMS J. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2025","DOI":"10.1007\/s00500-016-2465-7","article-title":"Optimization algorithms for the disjunctively constrained knapsack problem","volume":"22","author":"Salem","year":"2018","journal-title":"Soft Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1051\/ro\/2016049","article-title":"Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem","volume":"51","author":"Salem","year":"2017","journal-title":"RAIRO-Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"233","DOI":"10.7155\/jgaa.00186","article-title":"The knapsack problem with conflict graphs","volume":"13","author":"Pferschy","year":"2009","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1300","DOI":"10.1007\/s10878-016-0035-7","article-title":"Approximation of knapsack problems with conflict and forcing graphs","volume":"33","author":"Pferschy","year":"2017","journal-title":"J. Comb. Optim."},{"key":"ref_33","unstructured":"Milanic, M., and Monnot, J. (2008). Combinatorial Optimization-Theoretical Computer Science: Interfaces and Perspectives, Wiley-ISTE."},{"key":"ref_34","unstructured":"Gabrel, V. (2024, February 23). Dantzig-Wolfe Decomposition for Linearly Constrained Stable Set Problem; hal-00116732; France 2006. Available online: https:\/\/hal.science\/hal-00116732\/."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0377-2217(99)00015-6","article-title":"Conflict graphs in solving integer programming problems","volume":"121","author":"Nemhauser","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/BFb0120892","article-title":"Quadratic knapsack problems","volume":"Volume 12","author":"Padberg","year":"1980","journal-title":"Combinatorial Optimization"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF02612354","article-title":"Roof duality, complementations, and persistency in quadratic 0\u20131 optimization","volume":"28","author":"Hammer","year":"1984","journal-title":"Math. Program."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Punnen, A.P. (2022). The Quadratic Unconstrained Binary Optimization Problem: Theory, Algorithms, and Applications, Springer.","DOI":"10.1007\/978-3-031-04520-2"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Punnen, A.P. (2022). The Quadratic Unconstrained Binary Optimization Problem: Theory, Algorithms, and Applications, Springer.","DOI":"10.1007\/978-3-031-04520-2"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/j.orl.2011.01.006","article-title":"A well-solvable special case of the bounded knapsack problem","volume":"39","author":"Deineko","year":"2011","journal-title":"Oper. Res. Lett."},{"key":"ref_41","unstructured":"Larsen, K.G., Bodlaender, H.L., and Raskin, J.-F. (2017). 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik GmbH. Leibniz International Proceedings in Informatics."},{"key":"ref_42","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman Co."},{"key":"ref_43","unstructured":"Willis, W. (2011). Bounds for the Independence Number of a Graph. [Master\u2019s Thesis, College of Humanities and Sciences, Virginia Commonwealth University]."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"2150010","DOI":"10.1142\/S021759592150010X","article-title":"A Fast Algorithm for Knapsack Problem with Conflict Graph","volume":"38","author":"Li","year":"2021","journal-title":"Asia-Pac. J. Oper. Res."},{"key":"ref_45","first-page":"213","article-title":"Degr\u00e9s et nombre de stabilit\u00e9 d\u2019un graphe","volume":"17","author":"Hansen","year":"1975","journal-title":"Cah. Centre \u00c9tudes Rech. Op\u00e9r."},{"key":"ref_46","unstructured":"Borg, P. (2010). A sharp upper bound for the independence number. arXiv."},{"key":"ref_47","unstructured":"West, D. (2001). Introduction to Graph Theory, Prentice Hall Inc.. [2nd ed.]."},{"key":"ref_48","first-page":"4292","article-title":"The Network Data Repository with Interactive Graph Analytics and Visualization","volume":"29","author":"Rossi","year":"2015","journal-title":"Proc. AAAI"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1016\/j.ejor.2017.01.001","article-title":"Markov chain methods for the bipartite Boolean quadratic programming problem","volume":"260","author":"Karapetyan","year":"2017","journal-title":"Eur. J. Oper. Res."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/5\/219\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:44:27Z","timestamp":1760107467000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/5\/219"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,18]]},"references-count":49,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2024,5]]}},"alternative-id":["a17050219"],"URL":"https:\/\/doi.org\/10.3390\/a17050219","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,18]]}}}