# The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions
## 4 Integer Programming Formulations  
Let us now discuss some integer programming formulations of the KPCC. For each vertex \(i\in V\), let \(A(i)=\{j\in V:(i,j)\in E\}\) and the sets \(N_{i}(1),N_{i}(2),\ldots,N_{i}(p_{i})\) be a given partitionof \(A(i)\), where \(N_{i}(k)\
eq\emptyset\) for any \(k=1,2,\ldots p_{i}\), \(N_{i}(r)\cap N_{i}(s)=\emptyset\) whenever \(r\
eq s\), and \(A(i)=\cup_{k=1}^{p_{i}}N_{i}(k)\). Then, KPCC can be formulated as the 0-1 programming problem  
\[\text{StarIP: Maximize} \sum_{j\in V}c_{j}x_{j} \tag{3}\] \[\text{Subject to:} \sum_{j\in V}a_{j}x_{j}\leq b\] \[\sum_{j\in N_{i}(k)}x_{j}\leq|N_{i}(k)|(1-x_{i})\text{ for }k=1,2, \ldots p_{i},i=1,2,\ldots n\] \[x_{j}\in\{0,1\}\text{ for all }j\in V\]  
The above formulation reduces to the standard integer programming formulation of the KPCC when each \(N_{i}(k)\) is singleton, i.e., \(p_{i}=|A(i)|\) for all \(i\). When \(p_{i}=1\) for all \(i\) then \(N_{i}(1)=A(i)\), and the above integer program reduces to  
\[\text{MaxStarIP: Maximize} \sum_{j\in V}c_{j}x_{j} \tag{4}\] \[\text{Subject to:} \sum_{j\in V}a_{j}x_{j}\leq b\] \[\sum_{j\in A(i)}x_{j}\leq|A(i)|(1-x_{i})\text{ for }i=1,2,\ldots n\] \[x_{j}\in\{0,1\}\text{ for all }j\in V\]  
Thus, our general integer programming framework StarIP provides a class of integer programming formulations of KPCC that subsumes two well-studied formulations. Theorem 4.2: _Among all of the choices of the partition \(N_{i}(1),N_{i}(2),\ldots,N_{i}(p_{i})\) for StarIP, the standard formulation is the strongest and MaxStarIP is the weakest in terms of their LP relaxation values._  
Proof: Let \(\mathbf{x}^{*}=(x_{1}^{*},x_{2}^{*},\ldots,x_{n}^{*})\) be any feasible solution to the LP relaxation of the standard formulation. Then,  
\[x_{i}^{*}+x_{j}^{*}\leq 1\text{ for all }(i,j)\in E \tag{5}\]  
We successfully show that \(\mathbf{x}^{*}\) is a feasible solution to the LP relaxation of StarIP for any partition \(N_{i}(1),N_{i}(2),\ldots,N_{i}(p_{i})\). Choose a set \(N_{i}(k)\) for the vertex \(i\). Now, by adding the edge inequalities from (5) for all \((i,j)\in E\) such that \(j\in N_{i}(k)\), we obtain  
\[\sum_{j\in N_{i}(k)}(x_{i}^{*}+x_{j}^{*}\leq 1)=\sum_{j\in N_{i}(k)}x_{j}^{*} \leq|N_{i}(k)|\left(1-x_{i}^{*}\right).\]  
Thus, any feasible solution to the standard integer programming formulation of the KPCC is also a solution to the StarIP. Thus, the LP relaxation of the standard formulation is the strongest among the LP relaxation of any formulation within the class of StarIP. The second part of the theorem can be proved in an analogous way. Note that, for the LP relaxation of StarIP (for any choice of the partition of \(A(i)\)), \(x_{i}=\frac{1}{2}\) for all \(i\) as a feasible solution, provided that \(\frac{1}{2}\sum_{j\in V}a_{j}\leq b\). One way to strengthen or tighten StarIP is by computing upper bounds on the stability number of the subgraph \(G(i,k)\) induced by \(N_{i}(k)\). For example, if this subgraph is perfect, we can calculate the stability number exactly. If \(\alpha\) is the largest cardinality of a matching in this graph, then \(|N_{i}(k)|\) can be replaced by \(|N_{i}(k)|-\alpha\). Another way to tighten the formulation StarIP is as follows: let \(\gamma(i,k)\) be the objective function value of the LP relaxation of the standard formulation of KPCC restricted to \(G(i,k)\), where \(c_{i}=1\) for all \(i\). Then, \(|N_{i}(k)|\) can be replaced by \(\lfloor\gamma(i,k)\rfloor\). This number can be viewed as a fractional budgeted stability number. We can use other similar upper bounds to strengthen StarIP. For a review of different upper bounds that can be easily calculated, we refer to [43]. By tightening StarIP this way, we can obtain a better formulation for KPCC. Let \(A^{\prime}(i)=\{j\in V:(i,j)\in E,j<i\}\) and \(N^{\prime}_{i}(1)\), \(N^{\prime}_{i}(2),\ldots,N^{\prime}_{i}(p_{i})\) be a given partition of \(A^{\prime}(i)\). We can replace \(N_{i}(k)\) by \(N^{\prime}_{i}(k)\) in StarIP to obtain a valid formulation, say StarIP\({}^{\prime}\), of KPCC.