Home > Research > Publications & Outputs > Local and global lifted cover inequalities for ...

Research

Electronic data

Links

Text available via DOI:

Keywords

View graph of relations

Local and global lifted cover inequalities for the multidimensional knapsack problem

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Local and global lifted cover inequalities for the multidimensional knapsack problem. / Kaparis, Konstantinos; Letchford, A N.
In: European Journal of Operational Research, Vol. 186, No. 1, 01.04.2008, p. 91-103.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Kaparis, K & Letchford, AN 2008, 'Local and global lifted cover inequalities for the multidimensional knapsack problem', European Journal of Operational Research, vol. 186, no. 1, pp. 91-103. https://doi.org/10.1016/j.ejor.2007.01.032

APA

Kaparis, K., & Letchford, A. N. (2008). Local and global lifted cover inequalities for the multidimensional knapsack problem. European Journal of Operational Research, 186(1), 91-103. https://doi.org/10.1016/j.ejor.2007.01.032

Vancouver

Kaparis K, Letchford AN. Local and global lifted cover inequalities for the multidimensional knapsack problem. European Journal of Operational Research. 2008 Apr 1;186(1):91-103. doi: 10.1016/j.ejor.2007.01.032

Author

Kaparis, Konstantinos ; Letchford, A N. / Local and global lifted cover inequalities for the multidimensional knapsack problem. In: European Journal of Operational Research. 2008 ; Vol. 186, No. 1. pp. 91-103.

Bibtex

@article{4b3dd0cfe19d4682a22e1046a5f9c364,
title = "Local and global lifted cover inequalities for the multidimensional knapsack problem",
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 {\textquoteleft}global{\textquoteright} LCIs, which take the whole constraint matrix into account.",
keywords = " Integer programming, Combinatorial optimization",
author = "Konstantinos Kaparis and Letchford, {A N}",
year = "2008",
month = apr,
day = "1",
doi = "10.1016/j.ejor.2007.01.032",
language = "English",
volume = "186",
pages = "91--103",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier Science B.V.",
number = "1",

}

RIS

TY - JOUR

T1 - Local and global lifted cover inequalities for the multidimensional knapsack problem

AU - Kaparis, Konstantinos

AU - Letchford, A N

PY - 2008/4/1

Y1 - 2008/4/1

N2 - 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.

AB - 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.

KW - Integer programming

KW - Combinatorial optimization

U2 - 10.1016/j.ejor.2007.01.032

DO - 10.1016/j.ejor.2007.01.032

M3 - Journal article

VL - 186

SP - 91

EP - 103

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -