Optimization Online


On the exact separation of cover inequalities of maximum depth

Daniele Catanzaro (daniele.catanzaro***at***uclouvain.be)
Stefano Coniglio (s.coniglio***at***soton.ac.uk)
Fabio Furini (f.furini***at***iasi.cnr.it)

Abstract: 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.

Keywords: Knapsack Problem; Cover Inequalities; Dynamic Programming; Mixed Integer Nonlinear Programming; Cutting Plane Generation

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Other Topics (Dynamic Programming )


Download: [PDF]

Entry Submitted: 04/14/2020
Entry Accepted: 04/14/2020
Entry Last Modified: 05/15/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society