The Minmax Multidimensional Knapsack Problem with Application to a Chance-Constrained Problem
Loading...
Authors
Kress, Moshe
Penn, Michael
Polukarov, Maria
Subjects
knapsack problem
chance constraints
recourse
military logistics
combinatorial algorithm
chance constraints
recourse
military logistics
combinatorial algorithm
Advisors
Date of Issue
2007
Date
2007
Publisher
Language
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.
Type
Article
Description
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
2007 “The Minmax Multidimensional Knapsack Problem with Application to a Chance-Constrained Problem” (with M. Penn and M. Polukarov), Naval Research Logistics (NRL), V. 54, No. 6, pp 656-666.
Distribution Statement
Rights
defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.