The minmax multidimensional knapsack problem with application to a chance-constrained problem

被引：7
|
作者：
Kress, Moshe [1 ]
Penn, Michal
Polukarov, Maria
机构：
[1] Naval Postgrad Sch, Dept Operat Res, Monterey, CA USA
[2] Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel
来源：
NAVAL RESEARCH LOGISTICS | 2007年 / 54卷 / 06期
关键词：
knapsack problem; chance constraints; recourse; military logistics; combinatorial algorithm;
D O I：
10.1002/nav.20237
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper we present a new combinatorial problem, called minmax multidimensional knapsack problem (MKP), motivated by a military logistics problem. The logistics problem is a two-period, two-level, chance-constrained problem with recourse. We show that the MKP is NP-hard and develop a practically efficient combinatorial algorithm for solving it. We also show that under some reasonable assumptions regarding the operational setting of the logistics problem, the chance-constrained optimization problem is decomposable into a series of MKPs that are solved separately. (c) 2007 Wiley Periodicals, Inc.
引用
收藏
页码：656 / 666
页数：11
相关论文
共 50 条
  • [1] Chance-Constrained Submodular Knapsack Problem
    Chen, Junjie
    Maehara, Takanori
    COMPUTING AND COMBINATORICS, COCOON 2019, 2019, 11653 : 103 - 114
  • [2] Evolutionary Algorithms for the Chance-Constrained Knapsack Problem
    Xie, Yue
    Harper, Oscar
    Assimi, Hirad
    Neumann, Aneta
    Neumann, Frank
    PROCEEDINGS OF THE 2019 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'19), 2019, : 338 - 346
  • [3] A robust approach to the chance-constrained knapsack problem
    Klopfenstein, Olivier
    Nace, Dritan
    OPERATIONS RESEARCH LETTERS, 2008, 36 (05) : 628 - 632
  • [4] A PTAS for the chance-constrained knapsack problem with random item sizes
    Goyal, Vineet
    Ravi, R.
    OPERATIONS RESEARCH LETTERS, 2010, 38 (03) : 161 - 164
  • [5] Robust optimization approach for a chance-constrained binary knapsack problem
    Jinil Han
    Kyungsik Lee
    Chungmok Lee
    Ki-Seok Choi
    Sungsoo Park
    Mathematical Programming, 2016, 157 : 277 - 296
  • [6] Robust optimization approach for a chance-constrained binary knapsack problem
    Han, Jinil
    Lee, Kyungsik
    Lee, Chungmok
    Choi, Ki-Seok
    Park, Sungsoo
    MATHEMATICAL PROGRAMMING, 2016, 157 (01) : 277 - 296
  • [7] Estimation in chance-constrained problem
    Houda, Michal
    PROCEEDINGS OF THE 23RD INTERNATIONAL CONFERENCE ON MATHEMATICAL METHODS IN ECONOMICS 2005, 2005, : 134 - 139
  • [8] CHANCE-CONSTRAINED DISTRIBUTION PROBLEM
    REESE, RM
    STEDRY, AC
    NAVAL RESEARCH LOGISTICS, 1977, 24 (01) : 35 - 45
  • [9] Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications
    Li, Xuanfeng
    Liu, Shengcai
    Wang, Jin
    Chen, Xiao
    Ong, Yew-Soon
    Tang, Ke
    IEEE TRANSACTIONS ON CYBERNETICS, 2024, 54 (12) : 7969 - 7980
  • [10] Runtime Analysis of the (1+1) Evolutionary Algorithm for the Chance-Constrained Knapsack Problem
    Neumann, Frank
    Sutton, Andrew M.
    FOGA'19: PROCEEDINGS OF THE 15TH ACM/SIGEVO CONFERENCE ON FOUNDATIONS OF GENETIC ALGORITHMS, 2019, : 147 - 153
12345