# The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions
## 2 Literature Review  
Combinatorial optimization problems with conflict pair constraints have recently received considerable attention from the research community. These include conflict pair versions of the minimum spanning tree problem [11; 12; 13; 14; 19; 20], shortest path problem [14], minimum cost matching problem [14; 17], minimum cost bin packing [22; 23], and maximum flow problem [18]. KPCC is yet another member in this class of optimization problems. Conflict pair constraints can easily be absorbed into a quadratic objective function. Thus, these types of problems can be formulated as quadratic combinatorial optimization problems. However, the special structure of the conflict pair constraints makes the problem interesting to study independently. The multiple choice knapsack problem studied by [PERSON] et al. [24] and [PERSON] [25] in 1975 is essentially a KPCC, where the underlying graph is a collection of disjoint cliques. The continuous version of this problem was investigated by [PERSON] et al. [26]. Another special case of KPCC, where \(c_{j}=1\) for all \(j\), was mentioned by [PERSON] et al. [27] in the context of resource allocation. The general problem KPCC was introduced by [PERSON], [PERSON], and [PERSON] [10], and they proposed exact and heuristic algorithms to solve the problem. [PERSON] and [PERSON] [6] presented different exact algorithms based on MIP formulations. [PERSON], [PERSON], and [PERSON] [28] proposed yet another class of the branch and bound algorithm, along with extensive experimental analysis. Moreover, they presented comparisons of MIP formulations using general purpose solvers. [PERSON] et al. [29] investigated the convex hull of feasible solutions of KPCC, i.e., the KPCC polytope. The authors obtained necessary and sufficient conditions for odd cycle inequalities associated with the stable set problem to be facet-defining for the KPCC polytope. Similar conditions were developed for the cover inequalities of the knapsack polytope in connection with the KPCC polytope. They also analyzed different lifting procedures to obtain additional valid inequalities. Exploiting these inequalities, the authors proposed an effective branch and bound algorithm to solve KPCC and reported the results of extensive computational experiments. Heuristic algorithms for KPCC have been investigated by many researchers, and the results of extensive experimental analysis with these algorithms are available. [PERSON] and [PERSON] [5] developed a reactive-local-search-based algorithm and also generated a class of test instances based on the ideas from [10]. [PERSON] et al. [4] proposed local-branching-based heuristics and provided an experimental analysis based on instances generated by [5]. [PERSON] and [PERSON] [7] proposed a scatter-search-based metaheuristic algorithm along with results of an experimental analysis using test instances from [5]. Recently, [PERSON] [9] proposed an iterative-rounding-search-based algorithm. Their experimental results using test instances from [5] were promising and were able to obtain the best known solutions for many benchmark instances. [PERSON] et al. [30] developed a probabilistic tabu search algorithm to solve KPCC and reported extensive computational results. [PERSON] and [PERSON] [31] investigated KPCC for several special cases of the graph \(G\). They showed that KPCC can be solved in pseudo-polynomial time when \(G\) is a tree and more generally when \(G\) is a graph with bounded treewidth or chordal. Fully polynomial-time approximation schemes (FPTASs) are also derived for these classes of graphs. Further, they proved that KPCC remains strongly NP-hard on perfect graphs. It may be noted that the stable set problem is polynomial-time-solvable on perfect graphs. [PERSON] [1] also considered KPCC on trees, but the algorithm discussed in [31] is faster for this case. Moreover, [1] presents pseudopolynomial algorithms for cycles, forests, \(k\)-outerplanar graphs, and interval graphs.