Solving Multi-State Variable Dynamic Programming Models Using Vector Processing.
Abstract
One of the classical allocation models is known as the pallet loading problem. It consists of optimally loading parcels with various weight and volume parameters on a pallet. This pallet has weight and volume limits which constrain the amount of parcels that can be loaded. An optimal load is that combination of parcesl which maximized the summed utilities of all parcels that are loaded. The pallet loading problem can ge generalized to a 2-state variable (weight and volume) Dynamic Programming model. However, the problem can be solved by other methods. In the past, these other methods were preferred due to the difficulty of Dynamic Programming in solving problems of more than one state variable. With the advent of new computer technology in the form of vector processing, that difficulty can be overcome. The efficient column manipulating nature of vector processing is a perfect match for the column nature of the Dynamic Programming problem formulation. Based upon the algorithm developed using the ideas for vector processing, Dynamic Programming can be considered a very efficient solution technique to the 2-state variable problem. Using the vector processing capability of the ETA Systems supplied CDC Cyber 205, 2-state variable problems too large to be solved previously using DP can now be solved with small computational times. Also, an analysis of the results show that computation time increases linearly as the problem parameters are increased, not exponentially as is the case with other solution methods. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1985
- Accession Number
- ADA166763
Entities
People
- Stuart W. Stopkey
Organizations
- Air Force Institute of Technology