TITLE:
On Merging Cover Inequalities for Multiple Knapsack Problems
AUTHORS:
Randal Hickman, Todd Easton
KEYWORDS:
Multiple Knapsack Problem, Cutting Plane, Cover Inequality, Inequality Merging, Pseudocost, Integer Programming
JOURNAL NAME:
Open Journal of Optimization,
Vol.4 No.4,
December
25,
2015
ABSTRACT:
This paper describes methods to merge two cover inequalities and also simultaneously merge multiple cover inequalities in a multiple knapsack instance. Theoretical results provide conditions under which merged cover inequalities are valid. Polynomial time algorithms are created to find merged cover inequalities. A computational study demonstrates that merged inequalities improve the solution times for benchmark multiple knapsack instances by about 9% on average over CPLEX with default settings.