Making Gurobi Competitive with the Best Specialized Algorithms for the Multiple Knapsack Problem with Setups: Implications for OR Practitioners

An extension of the classic Knapsack Problem (KP) is the Multiple Knapsack Problem with Setups (MKPS). The MKPS has been used to model business applications that have previously been solved using approximate solution methods and implemented in industrial settings. In the operations research (OR) literature, there are a number of sophisticated solution approaches that, based on 360 MKPS instances typically used to test MKPS solution method performance, generate very good solutions. However, codes for these customized solution methods are typically not available for use by OR practitioners. In this paper, we use these same MKPS instances to demonstrate how well simple sequential increasing tolerance (SSIT) strategies combined with general-purpose integer programming software (Gurobi) can efficiently solve these MKPS instances. More importantly, it is shown both empirically and statistically that these simple approaches are as good as the best specialized methods in the literature. Hence, we present a methodology that is both easy for the OR practitioner to use and which gives results competitive with the best specialized MKPS solution methods in the literature without the need to generate algorithm-specific code. Finally, our approach is the only one that guarantees how close our solutions are to the optimums.