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 条

[11] Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem [J].

Pathiranage, Ishara Hewa ;

Neumann, Frank ;

Antipov, Denis ;

Neumann, Aneta .

PROCEEDINGS OF THE 2024 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, GECCO 2024, 2024, :520-528

[12] A novel branch-and-bound algorithm for the chance-constrained resource-constrained project scheduling problem [J].

Davari, Morteza ;

Demeulemeester, Erik .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2019, 57 (04) :1265-1282

[13] Deadline and Buffer Constrained Knapsack Problem [J].

Elgabli, Anis ;

Aggarwal, Vaneet .

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, 2019, 29 (05) :1564-1568

[14] Solving the Batch Stochastic Bin Packing Problem in Cloud: A Chance-constrained Optimization Approach [J].

Yan, Jie ;

Lu, Yunlei ;

Chen, Liting ;

Qin, Si ;

Fang, Yixin ;

Lin, Qingwei ;

Moscibroda, Thomas ;

Rajmohan, Saravan ;

Zhang, Dongmei .

PROCEEDINGS OF THE 28TH ACM SIGKDD CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING, KDD 2022, 2022, :2169-2179

[15] A Decomposition Algorithm for the Two-Stage Chance-Constrained Operating Room Scheduling Problem [J].

Najjarbashi, Amirhossein ;

Lim, Gino J. .

IEEE ACCESS, 2020, 8 (08) :80160-80172

[16] A randomized heuristic repair for the multidimensional knapsack problem [J].

Martins, Jean P. ;

Ribas, Bruno C. .

OPTIMIZATION LETTERS, 2021, 15 (02) :337-355

[17] A randomized heuristic repair for the multidimensional knapsack problem [J].

Jean P. Martins ;

Bruno C. Ribas .

Optimization Letters, 2021, 15 :337-355

[18] Hybrid Heuristic Algorithm for the Multidimensional Knapsack Problem [J].

Atilgan, Can ;

Nuriyev, Urfat .

2012 IV INTERNATIONAL CONFERENCE PROBLEMS OF CYBERNETICS AND INFORMATICS (PCI), 2012,

[19] Algorithm for Multi-Robot Chance-Constrained Generalized Assignment Problem with Stochastic Resource Consumption [J].

Yang, Fan ;

Chakraborty, Nilanjan .

2020 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS), 2020, :4329-4336

[20] Algorithm to Solve a Chance-Constrained Network Capacity Design Problem with Stochastic Demands and Finite Support [J].

Schumacher, Kathryn M. ;

Chen, Richard Li-Yang ;

Cohn, Amy E. M. ;

Castaing, Jeremy .

NAVAL RESEARCH LOGISTICS, 2016, 63 (03) :236-246

← 1 2 3 4 5 →