Approximate and Exact Merging of Knapsack Constraints with Cover Inequalities

This paper presents both approximate and exact merged knapsack cover inequalities, a class of cutting planes for knapsack and multiple knapsack integer programs. These inequalities combine the information from knapsack constraints and cover inequalities. Approximate merged knapsack cover inequalities can be generated through a O(n log n) algorithm, where n is the number of variables. This class of inequalities can be strengthened to an exact version with a pseudo-polynomial time algorithm. Computational experiments demonstrate an average improvement of approximately 8% in solution time and 5% in the number of ticks from CPLEX when approximate merged knapsack cover inequalities are implemented as preprocessing cuts to solve some benchmark multiple knapsack problems. Furthermore, exact merged knapsack cover inequalities improve the solution time and number of ticks of some random multiple knapsack instances by 15% and 5%, respectively