Cargo Loading Problem

A.I. McLeod

Abstract

The cargo loading problem is a special type of integer programming or optimization problem which can easily be solved by dynamic programming.  The problem is explained in detail in this notebook and the use of a companion Mathematica package for solving this problem is illustrated.  Some amusing timings with APL on computers of yesterday are made.

Keywords:  Optimization under constraint;  Integer Programming;  Dynamic Programming

Here the problem is to maximize the total value of all cargo items loaded on a vehicle with weight capacity K.  It is assumed that there are n items and that the weight of each item is (Subscript[w, i]) and is value is (Subscript[v, i])  for i = 1,  ...,  n.  This can be formulated as an integer programming problem:

\(TraditionalForm
    \`\(f\_n\)(K) = max\ \(∑\+\(i = 1\)\%n\( v\_i\) x\_i\)\)

subject to

\(TraditionalForm
    \`∑\+\(i = 1\)\%n\( w\_i\) x\_i ≤ K\)

where (Subscript[x, 1]),   ...  ,  (Subscript[x, n]) are nonnegative integer decision variables. A related problem is the Capital Budgeting Problem in which we have to choose which of n projects to fund given a total fund of K and assuming that the i-th project will require (Subscript[w, i]) units of capital and will produce a return of (Subscript[v, i]).  In this case the (Subscript[x, i]) are restricted to values of 0 or 1.  This can be handled by the additional constraints (Subscript[x, i]) ≤ (Subscript[q, i]) where (Subscript[q, i]) are set equal to 1 for the Capital Budgeting Problem and set to some large value in the usual Cargo Loading Problem.  The Cargo Loading Problem is also known in the literature as the Knapsack Problem.

This problem may be solved using the dynamic programming recursion:

(Subscript[f, i])(k)=({{max}, {0 ≤ (Subscript[x, i]) ≤ 
                    min( (Subscript[q, i]),  ⌊k/(Subscript[w, i])⌋ )}})  (Subscript[v, i])(Subscript[x, i])+(Subscript[f, i - 1])(k - (Subscript[w, i]),  (Subscript[x, i]))

where ⌊◼⌋ 
      , denotes the ceiling and (Subscript[f, 0])(k) = 0,  
      0 ≤ k ≤ K.   The optimal value is obtained by recursively evaluating (Subscript[f, n])(K).  First, we define the initial value of the optimal value function:

Next, the optimal value function for stage i = 1, 2,  ...,  n is defined.  The vectors of values, v, weights, w, and quantities, q are treated as global variables for the moment as global variables.  Computing time is greatly reduced by saving the results of the optimal value function results as they are calculated.  For each k and i, f[k,i] returns the vector of length k + 1, \(TraditionalForm
      \`{\(f\_i\)(k), \ \(x\_1\%*\), \ ...\ , \ \(x\_k\%*\)\ }\), where \(TraditionalForm\`\(x\_1\%*\), \ ...\ , \ \(x\_k\%*\)\) denote the optimized values of  (Subscript[x, 1]),  ... ,  (Subscript[x, k])  for that particular i and k.  The main function Cargo is just a shell which invokes the optimal value recursion function f as a local function:

Illustrative Use of the Package cargo.m

Set the file path in the following to whatever directory you have placed cargo.m in.

\(\(SetDirectory["c:\p\writalk\"]		\)\)

?Cargo

Suppose that there are 8 items and that an unlimited quantity of each item is available. The weight capacity is set at 81.  The profit per item is:  72 60 40 27 20 50 85 96 and the weight per item is 20 18 14 12 10 16 22 24.  Then since an unlimited supply is available we will set the (Subscript[q, i])'s to a large number, 99.

Timing[Cargo[k, v, w, q]]

which means maximum profit = 297, with x = (0,0,0,0,1,0,1,2).

Yesteryear Comparisons

Many years ago, I published an APL algorithm (McLeod, 1983) for the cargo loading problem. Over the years I have performed cpu timings with parameters as given  in the last section. There have been amazing improvements in speeds as well as quality of software. The Cyber computer listed was a state of the art mult-million dollar machine which required a huge staff. The VAX system was also very expensive, around $500,000 and required a lot of maintenance. I believe that the quality of the APL implementation on these machines was also inferior to that of APL*PLUS II. That's another story. When software became separated from the computer vendor in the PC revolution, quality improved greatly.

Table. CPU Benchmarks in APL

({{Machine and APL Version, Circa, CPU Time in Seconds}, {Cyber 825/NOS,  CDC APL17  .8, 1982, 17.8}, {VAX 785/11 VMS, 1985, 142.9}, {PC 286/7 10 MHZ,  APL*PLUS II, 1986, 72.6}, {IBM Thinkpad,  Pentium - 120, 1996, 2.0}})

Reference

McLeod, A.I. (1983). The cargo-loading or knapsack problem by dynamic programming, APL Quote Quad  14 .21-22.