# The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions
## 4 Integer Programming Formulations
### Benchmark Instances  
Our experiments used benchmark instances selected from [PERSON] et al. (2018) and instances generated using the DIMACS clique graph library ([PERSON] et al., 2018). The instances of [PERSON] et al. (2018) have three data sets: R1, R2, and R10. Each data set consists of eight classes, and each class has many instances. For the data set R1, in the first four classes, the items have a uniformly distributed weight from the range [20, 100], and the knapsack capacity is set to \(b=150\). The number \(n\) of items is 120, 250, 500, and 1000, respectively. The last four classes have uniformly distributed weights from [250, 500], and the knapsack capacity is set to \(b=1000\). The conflict graphs were generated randomly. For the data set R1, classes 1 to 4 have a total of 360 instances and classes 5 to 8 have a total of 360 instances. Thus, the data set R1 has a total of 720 instances. The data set R3 is similar to R1 except that the budget \(b\) is set to \(3\times 150=450\). Likewise, the data set R10 is almost identical to R1 except that the budget \(b\) is set to \(10\times 150=1500\). For details on these instances, we refer to the paper ([PERSON] et al., 2018). For our computational experiments, we selected instances from the first four classes of each of the data sets R1, R3, and R10. We categorized these instances further into small, medium, and large. The small instances consist of conflict graphs with 120 to 250 vertices, the medium instances consist of conflict graphs with 500 vertices, and the large instances consist of conflict graphs with 1000 vertices. From each category, we selected 120 instances using a prescribed selection rule. We refer to the aforementioned class of instances as random data instances. The DIMACS clique graph library consists of unweighted graphs. We generated two sets of KPCC benchmarks out of these instances, called positively correlated problems and negatively correlated problems. For positively correlated problems, the costs and weights have the same ordering, whereas for the negatively correlated problems, the costs and weights have opposite ordering. We used graphs that consist of 171 to 1024 vertices. These instances are further classified into small, medium, and large sizes. The small instances consist of graphs with 171 to 378 vertices, the medium instances consist of graphs with 400 to 500 vertices, and the large instances consist of 700 to 1024 vertices. There are 23 small instances, 24 medium instances, and 13 large instances. The DIMACS graphs were originally generated as clique benchmarks. To obtain stable set instances, we took the complement of these graphs. Let \(G=(V,E)\) be such a complement graph. For each \(i\in V\), we generated the cost \(c_{i}\) and the weight \(a_{i}\) as uniformly distributed random integers in the range \([1,|V|]\). To obtain positively correlated data, we first sort the vectors \(\mathbf{c}\) and \(\mathbf{a}\) in non-decreasing order \begin{table}
\begin{tabular}{l l l} \hline \hline  & **Bound** & **Name** \\ \hline UB1 & \(\lfloor\gamma(G)\rfloor\) & fractional budgeted stability number \\ UB2 & \(\lfloor\alpha_{f}(G)\rfloor\) & fractional stability number ([PERSON] et al., 2018) \\ UB3 & \(\lfloor\frac{1}{2}+\sqrt{\frac{1}{4}+|V|^{2}-|V|-2|E|}\rfloor\) & [PERSON] ([PERSON], 2018) \\ UB4 & \(\lfloor\frac{(\Delta-1)n+1}{2}\rfloor\) & [PERSON] ([PERSON], 2018) \\ UB5 & \(\lfloor|V|-\frac{|E|}{\Delta}\rfloor\) & [PERSON] ([PERSON], 2018) \\ UB6 & \(|V|-\delta\) & Minimum degree ([PERSON] et al., 2018) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Easily computable stability number bounds. and then apply the same random index permutation to both vectors. Negatively correlated instances are constructed in a similar manner but with opposite ordering. The budgets for the correlated instances are set as follows. First, we generate a random subset \(S\) of the vertices of \(G\) such that the cardinality of \(S\) is the known size of the maximum cardinality stable set on \(G\) and set \(b=\sum_{i\in S}a_{i}\).