Article ID: | iaor20082781 |
Country: | United States |
Volume: | 54 |
Issue: | 6 |
Start Page Number: | 656 |
End Page Number: | 666 |
Publication Date: | Sep 2007 |
Journal: | Naval Research Logistics |
Authors: | Kress Moshe, Penn Michal, Polukarov Maria |
Keywords: | military & defence |
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.