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

被引：31

作者：

Kaparis, Konstantinos ^{[1
]}

Letchford, Adam N. ^{[1
]}

机构：

[1] Univ Lancaster, Dept Management Sci, Lancaster LA1 4YW, England

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2008年 / 186卷 / 01期

基金：

英国工程与自然科学研究理事会;

关键词：

integer programming; combinatorial optimization;

D O I：

10.1016/j.ejor.2007.01.032

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：91 / 103

页数：13

共 26 条

[1]

[Anonymous], 2004, KNAPSACK PROBLEM

[2] Cover and pack inequalities for (Mixed) integer programming [J].

Atamtürk, A .

ANNALS OF OPERATIONS RESEARCH, 2005, 139 (01) :21-38

[3] FACETS OF KNAPSACK POLYTOPE [J].

BALAS, E .

MATHEMATICAL PROGRAMMING, 1975, 8 (02) :146-164

[4] FACETS OF KNAPSACK POLYTOPE FROM MINIMAL COVERS [J].

BALAS, E ;

ZEMEL, E .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1978, 34 (01) :119-148

[5] On separating cover inequalities for the multidimensional knapsack problem [J].

Bektas, Tolga ;

Oguz, Osman .

COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (06) :1771-1776

[6] GENERATING FENCHEL CUTTING PLANES FOR KNAPSACK POLYHEDRA [J].

Boyd, E. A. .

SIAM JOURNAL ON OPTIMIZATION, 1993, 3 (04) :734-750

[7] A genetic algorithm for the multidimensional knapsack problem [J].

Chu, PC ;

Beasley, JE .

JOURNAL OF HEURISTICS, 1998, 4 (01) :63-86

[8]

Chvatal V., 1973, Discrete Mathematics, V4, P305, DOI 10.1016/0012-365X(73)90167-2

[9] SOLVING LARGE-SCALE ZERO-ONE LINEAR-PROGRAMMING PROBLEMS [J].

CROWDER, H ;

JOHNSON, EL ;

PADBERG, M .

OPERATIONS RESEARCH, 1983, 31 (05) :803-834

[10] Solving multiple knapsack problems by cutting planes [J].

Ferreira, CE ;

Martin, A ;

Weismantel, R .

SIAM JOURNAL ON OPTIMIZATION, 1996, 6 (03) :858-877

← 1 2 3 →