# The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions
## 4 Integer Programming Formulations
### Experimental Results  
Let us now discuss the experimental outcomes of our analysis. First, we compared the standard KPCC formulation given in the introduction to MaxStarIP and its variations MaxStarIP1, MaxStarIP3, MaxStarIP5, and MaxStarIP6 using all of the test instances. Table 2 provides some insight into the relative strength of our formulations based on average running times (in seconds). The numbers marked in bold letters correspond to the lowest computational time taken. The experimental results disclose that there is no consistently superior formulation of KPCC among the ones we tested. The efficacy of various formulations could also be dependent on how tight the budget constraint is and what special structure the underlying graph has. Table 3 presents the experimental results after classifying the budget constraint in the test instances as tight, very tight, and moderately tight. Table 4 presents the experimental results after classifying the random test instances based on tightness of the budget constraints as well as the density of the underlying graph. We sometimes refer to a KPCC instance as sparse or dense. A _sparse (dense)_ KPCC instance has a sparse (dense) underlying graph. The results on the correlated test instances are classified only with respect to budget tightness since the density of the underlying graphs was uniform and generally sparse. These results are presented in Table 5.  
After this categorized analysis, the standard formulation appears as the preferred formulation overall, if one is constrained to recommend only one formulation. However, it may be noted that MaxStarIP appears to be more suited for sparse small instances with the tightest and loosest budgets. In addition, MaxStarIP outperforms the standard formulation on sparse medium and large instances with the tightest budgets. For our medium and large instances, as the underlying graph density increased the standard formulation became more robust than MaxStarIP. It is also important to point out that 8 out of 120 medium-sized instances were not solved to optimality within the time limit provided, either by the standard formulation or by the MaxStarIP type formulations. In addition, 30 of the 120 large instances with the loosest budget were not solved to optimality within the time limit specified by either of the aforementioned formulations. Now, let us compare the standard formulation and MaxStarIP type formulations over the correlated data. We found that the positively correlated instances were easier to solve than the negatively correlated instances. Increasing the budget within limits generally increased the running time of our formulations. Large negatively correlated instances often hit the time limit set for the experiments. The standard formulation generally outperformed \begin{table}
\begin{tabular}{l l l l l l l} \hline \hline
**Data Set** & **Standard** & **MaxStarIP** & **MaxStarIP1** & **MaxStarIP3** & **MaxStarIP5** & **MaxStarIP6** \\ \hline Random Small & **3.9525** & 4.1754 & 4.3713 & 9.2690 & 8.9970 & 9.2855 \\ Random Medium & 547.0358 & 546.1085 & **532.7913** & 542.4379 & 562.4661 & 540.5295 \\ Random Large & 1165.9380 & 1232.1670 & **1116.0310** & 1267.2090 & 1235.8030 & 1284.1800 \\ Positive Small & 0.4756 & 0.4833 & 0.4683 & 0.4874 & 0.4883 & **0.4606** \\ Positive Medium & 117.7284 & 108.5378 & 112.0652 & **105.2428** & 105.8007 & 109.7333 \\ Positive Large & 499.7824 & 506.0453 & 417.1473 & 418.3175 & 446.0069 & **407.9784** \\ Negative Smal & **1.3642** & 1.9495 & 1.7018 & 1.9759 & 1.7312 & 1.6509 \\ Negative Medium & 427.9115 & 499.4719 & 443.6538 & 431.8717 & 432.7311 & **422.1719** \\ Negative Large & 1866.9380 & 1937.1970 & 1780.2640 & 1723.5700 & **1698.0620** & 1742.0950 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Average running times (in seconds). MaxStarIP over our negatively correlated data set. We further observed that MaxStarIP is slightly better than the standard formulation for negatively correlated large instances with the loosest budget.