Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
477716 | European Journal of Operational Research | 2008 | 13 Pages |
Abstract
The 0–1 multidimensional knapsack problem (0–1 MKP) is a well-known (and strongly NPNP-hard) combinatorial optimization problem with many applications. Up to now, the majority of upper bounding techniques for the 0–1 MKP have been based on Lagrangian or surrogate relaxation. We show that good upper bounds can be obtained by a cutting plane method based on lifted cover inequalities (LCIs). As well as using traditional LCIs, we use some new ‘global’ LCIs, which take the whole constraint matrix into account.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Konstantinos Kaparis, Adam N. Letchford,