On the exact separation of cover inequalities of maximum-depth
(2022) Optimization Letters — Vol. 16, n° 2, p. 449-469 (2022)
Files
CORE_RP_3272.pdf
Open Access - Adobe PDF
- 2.23 MB
Details
- Authors
Coniglio, Stefano 
Furini, Fabio
- Abstract
- We investigate the problem of separating cover inequalities of maximum-depth exactly. We propose a pseudopolynomial-time dynamic-programming algorithm for its solution, thanks to which we show that this problem is weakly NP-hard (similarly to the problem of separating cover inequalities of maximum violation). We carry out extensive computational experiments on instances of the knapsack and the multi-dimensional knapsack problems with and without conflict constraints. The results show that, with a cutting-plane generation method based on the maximum-depth criterion, we can optimize over the cover-inequality closure by generating a number of cuts smaller than when adopting the standard maximum-violation criterion. We also introduce the Point-to-Hyperplane Distance Knapsack Problem (PHD-KP), a problem closely related to the separation problem for maximum-depth cover inequalities, and show how the proposed dynamic programming algorithm can be adapted for effectively solving the PHD-KP as well.
- Affiliations
Citations
Catanzaro, D., Coniglio, S., & Furini, F. (2022). On the exact separation of cover inequalities of maximum-depth. Optimization Letters, 16(2), 449-469. https://doi.org/10.1007/s11590-021-01741-0 (Original work published 2022)