# The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions
## 4 Integer Programming Formulations
### Experimental Results

Table 3: Average running times (in seconds) by budget. The frequency distribution of the fastest running times can provide further insight into the complexity of KPCC that averaging out the running times could not provide. For this analysis, we consider only the test instances that were solved to optimality within the time limit specified. In the event of a tie, any formulations in a tie for the fastest running time were considered to be equally good. From Table 6, we observe that the standard formulation is the preferred formulation followed by MaxStarIP1, and there is no clear winner for third place, based on frequency analysis. \begin{table}
\begin{tabular}{l l l l l l l l l} \hline \hline
**Data Set** & **Budget** & **Density** & **Standard** & **MaxStarIP** & **MaxStarIP1** & **MaxStarIP3** & **MaxStarIP5** & **MaxStarIP6** \\ \hline Random Small & very tight & 0.10-0.30 & 0.0657 & 0.04500 & **0.0421** & 40.7564 & 40.75 & 40.7564 \\ Random Small & tight & 0.10-0.30 & **0.1957** & 0.2893 & 0.2364 & 0.2621 & 0.2986 & 0.2707 \\ Random Small & moderate tight & 0.10-0.30 & 12.5571 & **12.3421** & 20.2229 & 17.135 & 17.52 & 18.2271 \\ \hline Random Small & very tight & 0.40-0.60 & 0.1557 & 0.1700 & **0.1486** & 0.1614 & 0.155 & 0.1586 \\ Random Small & tight & 0.40-0.60 & **0.7914** & 1.6179 & 0.8986 & 1.0443 & 0.9907 & 1.0564 \\ Random Small & moderate tight & 0.40-0.60 & 15.6157 & 15.7507 & **11.5864** & 12.2021 & 11.8821 & 12.4986 \\ \hline Random Small & very tight & 0.70-0.90 & 0.3092 & 0.4758 & **0.2892** & 0.5467 & 0.4867 & 0.4933 \\ Random Small & tight & 0.70-0.90 & 1.5700 & 2.5717 & 1.945 & 1.5833 & 1.6917 & 1.8108 \\ Random Small & moderate tight & 0.70-0.90 & 3.0409 & 3.1609 & **2.5572** & 5.5382 & 2.9364 & 5.3027 \\ \hline Random Medium & very tight & 0.10-0.30 & 0.3307 & 0.2493 & 0.2779 & 0.2471 & **0.2386** & 0.2421 \\ Random Medium & tight & 0.10-0.30 & **1.2657** & 1.8571 & 1.6014 & 2.3179 & 1.7207 & 1.7429 \\ Random Medium & moderate tight & 0.10-0.30 & 1807.6836 & 1792.2193 & 1933.2079 & 1802.3836 & 1830.6364 & **1778.0714** \\ \hline Random Medium & very tight & 0.40-0.60 & 0.91 & 0.8462 & 0.8869 & 0.8215 & 0.8654 & **0.8023** \\ Random Medium & tight & 0.40-0.60 & **16.8238** & 29.1508 & 18.8531 & 21.9731 & 23.0215 & 21.1769 \\ Random Medium & moderate tight & 0.40-0.60 & 2456.7877 & 2391.1946 & **2390.3023** & 2380.9877 & 2421.0185 & 2427.7085 \\ \hline Random Medium & very tight & 0.70-0.90 & **2.4708** & 4.3846 & 3.7431 & 4.7362 & 4.3208 & 4.7208 \\ Random Medium & tight & 0.70-0.90 & 58.4762 & 113.75 & **44.1023** & 134.3708 & 169.5746 & 92.7085 \\ Random Medium & moderate tight & 0.70-0.90 & 565.6369 & 569.3246 & **457.2462** & 520.4392 & 599.6292 & 525.4023 \\ \hline Random Large & very tight & 0.10-0.30 & 1.3021 & 1.2186 & 1.2957 & 1.1879 & 1.1857 & **1.1764** \\ Random Large & tight & 0.10-0.30 & **7.3279** & 12.9400 & 8.505 & 13.2321 & 8.8986 & 9.1857 \\ Random Large & moderate tight & 0.10-0.30 & **2475.0386** & 2547.7179 & 2487.0064 & 2504.4529 & 2519.53 & 2556.8364 \\ \hline Random Large & very tight & 0.40-0.60 & **4.3062** & 4.46062 & 5.6483 & 4.4131 & 4.5692 & 4.4046 \\ Random Large & tight & 0.40-0.60 & **211.7485** & 328.7346 & 303.8569 & 476.9715 & 466.3383 & 451.49 \\ Random Large & moderate tight & 0.40-0.60 & 3600.2546 & 3601.3262 & 3600.0577 & 3600.0585 & 3600.0592 \\ \hline Random Large & very tight & 0.70-0.90 & **11.4315** & 25.1323 & 31.7169 & 26.2469 & 27.8762 & 29.5338 \\ Random Large & tight & 0.70-0.90 & 1292.6946 & 1483.3115 & **1177.2792** & 1990.3762 & 1973.4069 & 2115.5815 \\ Random Large & moderate tight & 0.70-0.90 & 2967.3515 & 3171.7946 & **2494.4015** & 2886.62 & 2610.9469 & 2888.2269 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Average running times (in seconds) by budget and density.