The minmax multidimensional knapsack problem with application to a chance‐constrained problem |
| |
| Authors: | Moshe Kress Michal Penn Maria Polukarov |
| |
| Institution: | 1. Operations Research Department, Naval Postgraduate School, Monterey, CaliforniaOperations Research Department, Naval Postgraduate School, Monterey, California;2. Faculty of Industrial Engineering and Management, Technion, Haifa, Israel |
| |
| Abstract: | 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. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007 |
| |
| Keywords: | knapsack problem chance constraints recourse military logistics combinatorial algorithm |
|
|
