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
相关论文
共 50 条
  • [21] The Performance of the Modified Subgradient Algorithm on Solving the 0-1 Quadratic Knapsack Problem
    Sipahioglu, Aydin
    Sarac, Tugba
    INFORMATICA, 2009, 20 (02) : 293 - 304
  • [22] Adaptive and Cost-Optimal Parallel Algorithm for the 0-1 Knapsack Problem
    Li, Kenli
    Li, Lingxiao
    Tesfazghi, Teklay
    Sha, Edwin Hsing-Mean
    PROCEEDINGS OF THE 19TH INTERNATIONAL EUROMICRO CONFERENCE ON PARALLEL, DISTRIBUTED, AND NETWORK-BASED PROCESSING, 2011, : 537 - 544
  • [23] The performance of the modified subgradient algorithm on solving the 0-1 quadratic knapsack problem
    Sipahioglu, Aydin
    Sarac, Tugba
    20TH INTERNATIONAL CONFERENCE, EURO MINI CONFERENCE CONTINUOUS OPTIMIZATION AND KNOWLEDGE-BASED TECHNOLOGIES, EUROPT'2008, 2008, : 381 - 385
  • [24] Approaches for the 2D 0-1 Knapsack Problem with Conflict Graphs
    de Queiroz, Thiago Alves
    Miyazawa, Flavio Keidi
    PROCEEDINGS OF THE 2013 XXXIX LATIN AMERICAN COMPUTING CONFERENCE (CLEI), 2013,
  • [25] A practical efficient fptas for the 0-1 multi-objective knapsack problem
    Bazgan, Cristina
    Hugot, Hadrien
    Vanderpooten, Daniel
    ALGORITHMS - ESA 2007, PROCEEDINGS, 2007, 4698 : 717 - +
  • [26] Analysis of Divide-and-Conquer strategies for the 0-1 minimization knapsack problem
    Morales, Fernando A.
    Martinez, Jairo A.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 40 (01) : 234 - 278
  • [27] Implementing an efficient fptas for the 0-1 multi-objective knapsack problem
    Bazgan, Cristina
    Hugot, Hadrien
    Vanderpooten, Daniel
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 198 (01) : 47 - 56
  • [28] Approximate formulations for 0-1 knapsack sets
    Bienstock, Daniel
    OPERATIONS RESEARCH LETTERS, 2008, 36 (03) : 317 - 320
  • [29] Separation algorithms for 0-1 knapsack polytopes
    Konstantinos Kaparis
    Adam N. Letchford
    Mathematical Programming, 2010, 124 : 69 - 91
  • [30] Separation algorithms for 0-1 knapsack polytopes
    Kaparis, Konstantinos
    Letchford, Adam N.
    MATHEMATICAL PROGRAMMING, 2010, 124 (1-2) : 69 - 91
12345