Home » Publication » 27522

Dettaglio pubblicazione

2022, OPTIMIZATION LETTERS, Pages 449-469 (volume: 16)

On the exact separation of cover inequalities of maximum-depth (01a Articolo in rivista)

Catanzaro D., Coniglio S., Furini F.

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.
Gruppo di ricerca: Combinatorial Optimization
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma