An Algorithm for Nonlinear Knapsack Problems.

Abstract

A recursive algorithm for the solution of separable nonlinear multidimensional knapsack problems is developed by exploiting discontinuity preserving properties of the maximal convolution. The curse of dimensionality, which is usually associated with dynamic programming type algorithms, is successfully mitigated by reducing an M-dimensional dynamic program to a 1-dimensional dynamic program through the use of the imbedded state space approach. Computational experience with the algorithm on problems with as many as 10 state variables is also reported and several interesting extensions are discussed. (Author)

Document Details

Document Type
Technical Report
Publication Date
May 01, 1974
Accession Number
AD0780929

Entities

People

  • Roy E. Marsten
  • Thomas L. Morin

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Convolution
  • Discontinuities
  • Dynamic Programming
  • Evolutionary Algorithms
  • Heuristic Methods
  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Mathematical Modeling and Probability Theory.

Technology Areas

  • Space