12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Local and global lifted cover inequalities for ...
View graph of relations

« Back

Local and global lifted cover inequalities for the multidimensional knapsack problem

Research output: Contribution to journalJournal article

Published

Journal publication date1/04/2008
JournalEuropean Journal of Operational Research
Journal number1
Volume186
Number of pages13
Pages91-103
Original languageEnglish

Abstract

The 0-1 Multidimensional Knapsack Problem (0-1 MKP) is a well-known (and strongly NP-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.