We investigate the problem of exactly separating cover inequalities of maximum depth and we develop a pseudo-polynomial-time algorithm for this purpose. Compared to the standard method based on the maximum violation, computational experiments carried out on knapsack and multi-dimensional knapsack instances show that, with a cutting-plane method based on the maximum-depth criterion, we can optimize over the closure of the cover inequalities in a smaller number of cuts. These results encourage the research of efficient exact and heuristic separation algorithms based on maximizing the cut depth, also for other classes of valid inequalities.
Article
View On the exact separation of cover inequalities of maximum depth