# The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions
## 4 Integer Programming Formulations
### Experimental Results
For positively correlated data, MaxStarIP is best suited for medium instances and the standard formulation is the strongest for our small and large instances. It may also be noted that the standard formulation is the most robust in terms of running times, followed by MaxStarIP1, and there is no clear formulation that wins third place. MaxStarIP1 outperformed our other KPCC formulations over denser and larger random instances, while the standard formulation showed superiority on sparser large random instances. Each of the formulations MaxStartIP, MaxStarIP3, MaxStarIP5, and MaxStarIP6 were found to be the preferred formulation for at least one of the random data set classifications in Table 4. Based on this, we conclude that there is no one formulation that is best suited for our positively correlated data set. The standard formulation is best suited for our medium and small negatively correlated data. In addition, MaxStarIP3 outperformed the other formulations over our larger negatively correlated instances with the tightest budgets, and MaxStarIP5 outperformed the other formulations in Table 5 for the remaining large negatively correlated KPCC instances. \begin{table}
\begin{tabular}{l l l l l l l} \hline \hline
**Data Set** & **Budget** & **Standard** & **MaxStarIP** & **MaxStarIP1** & **MaxStarIP3** & **MaxStarIP5** & **MaxStarIP6** \\ \hline Random Small & very tight & 0.17025 & 0.2180 & **0.1535** & 14.48525 & 14.46275 & 14.4683 \\ Random Small & tight & **0.8165** & 1.4390 & 0.98075 & 0.93225 & 0.95875 & 1.0078 \\ Random Small & moderate tight & 10.871 & **10.86925** & 11.97975 & 12.3895 & 11.56975 & 12.3805 \\ \hline Random Medium & very tight & **1.2145** & 1.78725 & 1.602 & 1.89275 & 1.769 & 1.87975 \\ Random Medium & tight & 24.9155 & 47.09275 & **21.021** & 51.623 & 63.196 & 37.62275 \\ Random Medium & moderate tight & 1614.97725 & 1589.4455 & 1575.751 & 1573.798 & 1622.43325 & **1582.0860** \\ \hline Random Large & very tight & **5.5705** & 10.0915 & 12.59575 & 10.38025 & 10.95975 & 11.4418 \\ Random Large & tight & 491.50875 & 593.444 & 484.346 & 806.51925 & **796.03675** & 837.51325 \\ Random Large & moderate tight & 3000.7355 & 3092.9655 & **2851.1515** & 2984.729 & 2900.411 & 3003.5857 \\ \hline Positive Small & very tight & 0.2232 & **0.1991** & 0.2173 & 0.2155 & 0.2045 & 0.2245 \\ Positive Small & tight & 0.4123 & **0.3786** & 0.4532 & 0.4936 & 0.4955 & 0.4745 \\ Positive Small & moderate tight & 0.7914 & 0.8723 & 0.7345 & 0.7532 & 0.7650 & **0.6827** \\ \hline Positive Medium & very tight & 5.4561 & 4.7843 & 3.5357 & 3.6765 & 3.6857 & 3.7887 \\ Positive Medium & tight & 47.9278 & 33.6848 & 35.3148 & 32.3804 & **29.4691** & 32.3991 \\ Positive Medium & moderate tight & 299.8013 & 287.1443 & 297.34522 & **279.6713** & 284.2474 & 293.0122 \\ \hline Positive Large & very tight & **29.4941** & 35.5012 & 41.20824 & 45.17471 & 47.0088 & 41.72882 \\ Positive Large & moderate tight & 1093.12647 & 1082.2853 & 918.3300 & 919.5976 & 959.8629 & **908.9182** \\ Positive Large & tight & 376.7265 & 400.34941 & 291.9035 & 290.1800 & 331.1488 & **273.2882** \\ \hline Negative Small & very tight & **0.3973** & 0.4814 & 0.52410 & 0.5064 & 0.4745 & 0.4614 \\ Negative Small & tight & **0.9173** & 1.2236 & 1.17409 & 1.2859 & 1.13911 & 1.3295 \\ Negative Small & moderate tight & **2.7782** & 4.1436 & 3.4073 & 4.1354 & 3.5800 & 3.1618 \\ \hline Negative Medium & very tight & **6.5067** & 10.5179 & 7.8883 & 9.2575 & 9.2071 & 8.8704 \\ Negative Medium & tight & **266.1083** & 292.6083 & 276.6429 & 274.4096 & 299.2258 & 270.0600 \\ Negative Medium & moderate tight & 1011.11958 & 1195.2896 & 1046.4300 & 1011.9479 & 989.7604 & **987.5854** \\ \hline Negative Large & very tight & 721.0029 & 857.0400 & 667.3035 & **649.35523** & 666.8012 & 658.71412 \\ Negative Large & tight & 2095.2776 & 2210.1188 & 2010.5912 & 1965.06882 & **1879.2935** & 1955.7835 \\ Negative Large & moderate tight & 2784.5333 & 2744.4318 & 2662.8976 & 2556.2859 & **2548.0912** & 2611.7882 \\ \hline \hline \end{tabular}
\end{table}