The Minmax Multidimensional Knapsack Problem with Application to a Chance-Constrained Problem

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 17, 2007
Accession Number
ADA487134

Entities

People

  • Maria Polukarov
  • Michal Penn
  • Moshe Kress

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Weapons Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Ammunition
  • Artillery
  • Deployment
  • Inventory
  • Inventory Control
  • Logistics
  • Military Operations
  • Military Research
  • Operations Research
  • Optimization
  • Probability
  • Probability Distributions
  • Random Variables
  • Stockpiles
  • Supply Chain
  • Weapons

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Operations Research