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 条
  • [41] New binary marine predators optimization algorithms for 0-1 knapsack problems
    Abdel-Basset, Mohamed
    Mohamed, Reda
    Chakrabortty, Ripon K.
    Ryan, Michael
    Mirjalili, Seyedali
    COMPUTERS & INDUSTRIAL ENGINEERING, 2021, 151
  • [42] A Stochastic Local Search Heuristic for the Multidimensional Multiple-choice Knapsack Problem
    Xia, Youxin
    Gao, Chao
    Li, JinLong
    BIO-INSPIRED COMPUTING - THEORIES AND APPLICATIONS, BIC-TA 2015, 2015, 562 : 513 - 522
  • [43] A novel binary Kepler optimization algorithm for 0-1 knapsack problems: Methods and applications
    Abdel-Basset, Mohamed
    Mohamed, Reda
    Hezam, Ibrahim M.
    Sallam, Karam M.
    Alshamrani, Ahmad M.
    Hameed, Ibrahim A.
    ALEXANDRIA ENGINEERING JOURNAL, 2023, 82 : 358 - 376
  • [44] A variable relationship excavating based optimization algorithm for solving 0-1 knapsack problems
    Zheng, Minyi
    Gu, Fangqing
    Chen, Xuesong
    Wu, Hao-Tian
    2019 15TH INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND SECURITY (CIS 2019), 2019, : 36 - 39
  • [45] A Novel Binary Artificial Jellyfish Search Algorithm for Solving 0-1 Knapsack Problems
    Yildizdan, Gulnur
    Bas, Emine
    NEURAL PROCESSING LETTERS, 2023, 55 (07) : 8605 - 8671
  • [46] Modified symbiotic organisms search (MSOS) algorithm for solving 0-1 Knapsack problems
    Mandal, Ranjit Kumar
    Mukherjee, Pinaki
    Maitra, Mausumi
    OPSEARCH, 2024,
  • [47] A local-search-based heuristic for the demand-constrained multidimensional knapsack problem
    Cappanera, P
    Trubian, M
    INFORMS JOURNAL ON COMPUTING, 2005, 17 (01) : 82 - 98
  • [48] Exploring the Impact of Local Operator Configurations in the Multi-Demand Multidimensional Knapsack Problem
    Garcia, Jose
    Cattarinich, Ivo
    Moraga, Paola
    Pinto, Hernan
    APPLIED SCIENCES-BASEL, 2025, 15 (04):
  • [49] An Evolutionary Algorithm with Masked Mutation for 0/1 Knapsack Problem
    Khan, Mozammel H. A.
    2013 INTERNATIONAL CONFERENCE ON INFORMATICS, ELECTRONICS & VISION (ICIEV), 2013,
  • [50] Solving 0–1 Knapsack Problem using Cohort Intelligence Algorithm
    Anand J. Kulkarni
    Hinna Shabir
    International Journal of Machine Learning and Cybernetics, 2016, 7 : 427 - 441
12345