Determining when Gurobi can Optimally Solve the Quadratic Knapsack Problem with Conflict Graphs: Implications for OR Practitioners

The Quadratic Knapsack Problem with Conflict Graphs (QKPCG) was introduced in a 2017 paper along with 45 QKPCG test instances. Since then, none of the solution methods presented in the literature have been designed to generate proven optimums or even any measure of how close the solutions are to the optimums. In this paper, the original 45 QKPCG test instances are extended to a more comprehensive set of 810 test instances (765 new instances). The reason for expanding the test instances is that the original 45 QKPCG instances were very limited in scope. This more comprehensive set of test instances provides the opportunity to determine, when using general-purpose integer programming software (Gurobi), how solution difficulty changes when the conflict graph density changes, as well as the density of the quadratic profit terms (pijs). Since Gurobi is widely used in industry to solve optimization problems, these results can provide practical knowledge to operations research (OR) practitioners. Additionally, the benefit of using solutions generated by a hybrid search method (HSM) available in the literature as input to Gurobi when the pij densities are 75% or greater is demonstrated. However, when the pij densities are less than 75%, the use of HSM solutions as input to Gurobi is shown to be of no benefit. Over the 810 test instances, Gurobi determined proven optimums for over 93% of them (99% when the density of the quadratic profit terms is less than 75%). Finally, although no new theory or exact algorithm is presented, this is the first time a QKPCG solution procedure that strives to obtain proven optimums is discussed in the literature. The simplicity and ease of implementation of this approach make it very attractive for use by OR practitioners.