(***********************************************************************
Mathematica-Compatible Notebook
This notebook can be used on any computer system with Mathematica 3.0,
MathReader 3.0, or any compatible application. The data for the notebook
starts with the line of stars above.
To get the notebook into a Mathematica-compatible application, do one of
the following:
* Save the data starting with the line of stars above into a file
with a name ending in .nb, then open the file inside the application;
* Copy the data starting with the line of stars above to the
clipboard, then use the Paste menu command inside the application.
Data for notebooks contains only printable 7-bit ASCII and can be
sent directly in email or through ftp in text mode. Newlines can be
CR, LF or CRLF (Unix, Macintosh or MS-DOS style).
NOTE: If you modify the data for this notebook not in a Mathematica-
compatible application, you must delete the line below containing the
word CacheID, otherwise Mathematica-compatible applications may try to
use invalid cache data.
For more information on notebooks and Mathematica-compatible
applications, contact Wolfram Research:
web: http://www.wolfram.com
email: info@wolfram.com
phone: +1-217-398-0700 (U.S.)
Notebook reader applications are available free of charge from
Wolfram Research.
***********************************************************************)
(*CacheID: 232*)
(*NotebookFileLineBreakTest
NotebookFileLineBreakTest*)
(*NotebookOptionsPosition[ 12428, 413]*)
(*NotebookOutlinePosition[ 13716, 454]*)
(* CellTagsIndexPosition[ 13672, 450]*)
(*WindowFrame->Normal*)
Notebook[{
Cell[CellGroupData[{
Cell["Cargo Loading Problem", "Title"],
Cell["A.I. McLeod ", "Author",
TextAlignment->Center],
Cell["\<\
Department of Statistical and Actuarial Sciences,
University of Western Ontario,
London, Ontario N6A 5B7\
\>", "Address"],
Cell["aim@uwo.ca", "Address"],
Cell["http://www.stats.uwo.ca/mcleod", "Address"],
Cell[CellGroupData[{
Cell["Abstract", "Section"],
Cell[TextData[{
"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 ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" package for solving this problem is illustrated. Some amusing timings \
with APL on computers of yesterday are made."
}], "Abstract"],
Cell[TextData[{
StyleBox["Keywords",
FontWeight->"Bold"],
": Optimization under constraint; Integer Programming; Dynamic \
Programming"
}], "Abstract"]
}, Open ]],
Cell[CellGroupData[{
Cell["Description of the Problem", "SectionFirst"],
Cell[TextData[{
"Here the problem is to maximize the total value of all cargo items loaded \
on a vehicle with weight capacity ",
Cell[BoxData[
\(TraditionalForm\`K\)]],
". It is assumed that there are ",
Cell[BoxData[
\(TraditionalForm\`n\)]],
" items and that the weight of each item is ",
Cell[BoxData[
\(TraditionalForm\`w\_i\)]],
" and is value is ",
Cell[BoxData[
\(TraditionalForm\`v\_i\)]],
" for ",
Cell[BoxData[
\(TraditionalForm\`i = 1, \ ..., \ n\)]],
". This can be formulated as an integer programming problem:"
}], "Text"],
Cell[TextData[Cell[BoxData[
\(TraditionalForm
\`\(f\_n\)(K) = max\ \(\[Sum]\+\(i = 1\)\%n\( v\_i\) x\_i\)\)]]],
"NumberedEquation",
TextAlignment->Center,
FontSize->13],
Cell["subject to", "Text"],
Cell[TextData[Cell[BoxData[
\(TraditionalForm
\`\[Sum]\+\(i = 1\)\%n\( w\_i\) x\_i \[LessEqual] K\)]]],
"NumberedEquation",
TextAlignment->Center,
FontSize->13],
Cell[TextData[{
"where ",
Cell[BoxData[
\(TraditionalForm\`x\_1, \ ... \ , \ x\_n\)]],
" are nonnegative integer decision variables. A related problem is the \
Capital Budgeting Problem in which we have to choose which of ",
Cell[BoxData[
\(TraditionalForm\`n\)]],
" projects to fund given a total fund of ",
Cell[BoxData[
\(TraditionalForm\`K\)]],
" and assuming that the ",
Cell[BoxData[
\(TraditionalForm\`i\)]],
"-th project will require ",
Cell[BoxData[
\(TraditionalForm\`w\_i\)]],
" units of capital and will produce a return of ",
Cell[BoxData[
\(TraditionalForm\`v\_i\)]],
". In this case the ",
Cell[BoxData[
\(TraditionalForm\`x\_i\)]],
" are restricted to values of 0 or 1. This can be handled by the \
additional constraints ",
Cell[BoxData[
\(TraditionalForm\`x\_i \[LessEqual] q\_i\)]],
" where ",
Cell[BoxData[
\(TraditionalForm\`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."
}], "Text"],
Cell["\<\
This problem may be solved using the dynamic programming recursion:\
\
\>", "Text"],
Cell[TextData[Cell[BoxData[
FormBox[
RowBox[{\(\(f\_i\)(k)\), "=",
RowBox[{
RowBox[{GridBox[{
{"max"},
{
\(0 \[LessEqual] x\_i \[LessEqual]
min(\ q\_i, \ \[LeftFloor]k/w\_i\[RightFloor]\ )\)}
}], " ", \(v\_i\), \(x\_i\)}], "+",
\(\(f\_\(i - 1\)\)(k - w\_i, \ x\_i)\)}]}], TraditionalForm]]]],
"NumberedEquation",
TextAlignment->Center,
FontSize->13],
Cell[TextData[{
"where ",
Cell[BoxData[
\(TraditionalForm\`\(\[LeftFloor]\[FilledSmallSquare]\[RightFloor]\
\)\)]],
", denotes the ceiling and ",
Cell[BoxData[
\(TraditionalForm\`\(f\_0\)(k) = 0, \
0 \[LessEqual] k \[LessEqual] K\)]],
". The optimal value is obtained by recursively evaluating ",
Cell[BoxData[
\(TraditionalForm\`\(f\_n\)(K)\)]],
". First, we define the initial value of the optimal value function:"
}], "Text"],
Cell[BoxData[
\(\(f[k_, \ 0]\ = \ {0}; \)\)], "InputOnly",
CellLabel->"In[1]:="],
Cell[TextData[{
"Next, the optimal value function for stage ",
Cell[BoxData[
\(TraditionalForm\`i = 1, 2, \ ..., \ n\)]],
" is defined. The vectors of values, ",
Cell[BoxData[
\(TraditionalForm\`v\)],
FontWeight->"Bold"],
", weights, ",
Cell[BoxData[
FormBox[
StyleBox["w",
FontWeight->"Bold"], TraditionalForm]]],
", and quantities, ",
Cell[BoxData[
FormBox[
RowBox[{
StyleBox["q",
FontWeight->"Bold"], " "}], TraditionalForm]]],
"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 ",
Cell[BoxData[
\(TraditionalForm\`k\)]],
" and ",
Cell[BoxData[
\(TraditionalForm\`i\)]],
", ",
StyleBox["f[k,i]",
FontWeight->"Bold"],
" returns the vector of length ",
Cell[BoxData[
\(TraditionalForm\`k + 1\)]],
", ",
Cell[BoxData[
\(TraditionalForm
\`{\(f\_i\)(k), \ \(x\_1\%*\), \ ...\ , \ \(x\_k\%*\)\ }\)]],
", where ",
Cell[BoxData[
\(TraditionalForm\`\(x\_1\%*\), \ ...\ , \ \(x\_k\%*\)\)]],
" denote the optimized values of ",
Cell[BoxData[
\(TraditionalForm\`x\_1, \ ...\ , \ x\_k\)]],
" for that particular ",
Cell[BoxData[
\(TraditionalForm\`i\)]],
" and ",
Cell[BoxData[
\(TraditionalForm\`k\)]],
". ",
"The main function Cargo is just a shell which invokes the optimal value \
recursion function ",
StyleBox["f ",
FontWeight->"Bold"],
"as a local function:"
}], "Text"]
}, Open ]],
Cell[CellGroupData[{
Cell["Illustrative Use of the Package cargo.m", "Section"],
Cell["\<\
Set the file path in the following to whatever directory you have \
placed cargo.m in.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[
\(\(SetDirectory["\"]\t\t\)\)], "Input",
CellLabel->"In[1]:="],
Cell[BoxData[
\("c:\\p\\writalk"\)], "Output",
CellLabel->"Out[1]="]
}, Open ]],
Cell[BoxData[
\(<< cargo.m\)], "InputOnly",
CellLabel->"In[2]:="],
Cell[CellGroupData[{
Cell[BoxData[
\(\(?Cargo\)\)], "Input",
CellLabel->"In[3]:="],
Cell[BoxData[
\("Cargo[k,v,w,q] solves the integer programming problem, \
maximize v x subject to x>=0 and w x <= k and x <= q, where k is the \
right-hand side in the linear inequality constraint and v, w and q denote \
vectors of length n containing respectively the coefficients in the objective \
function, linear constraint and quantities available. The function returns a \
vector of length n+1 containing the optimal values of first the objective \
function and then the n decision variables."\)], "Print"]
}, Open ]],
Cell[TextData[{
"\nSuppose that there are 8 items and that an unlimited quantity of each \
item is available. The weight capacity is set at ",
Cell[BoxData[
\(TraditionalForm\`81\)]],
". T",
"he 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 ",
Cell[BoxData[
\(TraditionalForm\`q\_i\)]],
"'s to a large number, ",
Cell[BoxData[
\(TraditionalForm\`99\)]],
"."
}], "Text"],
Cell[BoxData[
RowBox[{
StyleBox[\(v\ = \ {72, \ 60, \ 40, \ 27, \ 20, \ 50, \ 85, \ 96}\),
FontFamily->"Courier New"],
StyleBox[";",
FontFamily->"Courier New"],
StyleBox["\n",
FontSize->12],
StyleBox[\(w = \ {20, \ 18, \ 14, \ 12, \ 10, \ 16, \ 22, \ 24}\),
FontFamily->"Courier New"],
StyleBox[";",
FontFamily->"Courier New"],
StyleBox["\n",
FontSize->12],
StyleBox[\(q\ = \ {99, \ 99, \ 99, \ 99, \ 99, \ 99, \ 99, \ 99}\),
FontFamily->"Courier New"],
StyleBox[";",
FontFamily->"Courier New"], "\n", \(k = 81\), ";"}]], "InputOnly",
CellLabel->"In[4]:="],
Cell[CellGroupData[{
Cell[BoxData[
\(Timing[Cargo[k, v, w, q]]\)], "Input",
CellLabel->"In[5]:="],
Cell[BoxData[
\({0.989999999999999857`\ Second, {297, 0, 0, 0, 0, 1, 0, 1, 2}}\)],
"Output",
CellLabel->"Out[5]="]
}, Open ]],
Cell["\<\
which means maximum profit = 297, with x = (0,0,0,0,1,0,1,2). \
\>", "Text"]
}, Open ]],
Cell[CellGroupData[{
Cell["Yesteryear Comparisons", "Section"],
Cell["\<\
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.\
\>", "Text"],
Cell[CellGroupData[{
Cell[TextData[StyleBox["Table. CPU Benchmarks in APL",
FontWeight->"Bold"]], "Subsubsection"],
Cell[TextData[Cell[BoxData[
FormBox[GridBox[{
{
StyleBox[\(Machine\ and\ APL\ Version\),
FontFamily->"arial",
FontWeight->"Bold"],
StyleBox["Circa",
FontWeight->"Bold"],
StyleBox[\(CPU\ Time\ in\ Seconds\),
FontFamily->"arial",
FontWeight->"Bold"]},
{
StyleBox[\(Cyber\ 825/NOS, \ CDC\ APL17 .8\),
FontFamily->"arial"], "1982", "17.8"},
{
StyleBox[\(VAX\ 785/11\ VMS\),
FontFamily->"arial"], "1985", "142.9"},
{
StyleBox[\(PC\ 286/7\ 10\ MHZ, \ APL*PLUS\ II\),
FontFamily->"arial"], "1986", "72.6"},
{\(IBM\ Thinkpad, \ Pentium - 120\), "1996", "2.0"}
}], TraditionalForm]]]], "Program"]
}, Open ]]
}, Open ]],
Cell[CellGroupData[{
Cell["Reference", "Section"],
Cell["\<\
McLeod, A.I. (1983). The cargo-loading or knapsack problem by \
dynamic programming, APL Quote Quad 14 .21-22.\
\>", "Text"]
}, Open ]]
}, Open ]]
},
FrontEndVersion->"Macintosh 3.0",
ScreenRectangle->{{0, 800}, {0, 580}},
ScreenStyleEnvironment->"Working",
PrintingStyleEnvironment->"Printout",
WindowToolbars->{},
WindowSize->{732, 553},
WindowMargins->{{4, Automatic}, {Automatic, 1}},
PrintingCopies->1,
PrintingPageRange->{Automatic, Automatic},
PrintingOptions->{"PrintingMargins"->{{36, 36}, {36, 36}},
"PaperSize"->{612, 792},
"PaperOrientation"->"Portrait",
"PrintCellBrackets"->False,
"PrintRegistrationMarks"->False,
"PrintMultipleHorizontalPages"->False,
"Magnification"->1},
Magnification->1,
StyleDefinitions -> "ArticleModern.nb",
MacintoshSystemPageSetup->"\<\
00<0001804P000000]P2:?oQon82n@960dL5:0?l0080001804P000000]P2:001
0000I00000400`<300000BL?00400@0000000000000006P801T1T00000000000
00000000000000000000000000000000\>"
]
(***********************************************************************
Cached data follows. If you edit this Notebook file directly, not using
Mathematica, you must remove the line containing CacheID at the top of
the file. The cache data will then be recreated when you save this file
from within Mathematica.
***********************************************************************)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[CellGroupData[{
Cell[1731, 51, 38, 0, 69, "Title"],
Cell[1772, 53, 55, 1, 40, "Author"],
Cell[1830, 56, 131, 4, 52, "Address"],
Cell[1964, 62, 29, 0, 20, "Address"],
Cell[1996, 64, 49, 0, 20, "Address"],
Cell[CellGroupData[{
Cell[2070, 68, 27, 0, 63, "Section"],
Cell[2100, 70, 438, 8, 78, "Abstract"],
Cell[2541, 80, 162, 5, 50, "Abstract"]
}, Open ]],
Cell[CellGroupData[{
Cell[2740, 90, 50, 0, 71, "SectionFirst"],
Cell[2793, 92, 592, 18, 40, "Text"],
Cell[3388, 112, 183, 5, 28, "NumberedEquation"],
Cell[3574, 119, 26, 0, 24, "Text"],
Cell[3603, 121, 175, 5, 28, "NumberedEquation"],
Cell[3781, 128, 1170, 33, 88, "Text"],
Cell[4954, 163, 93, 3, 24, "Text"],
Cell[5050, 168, 484, 13, 43, "NumberedEquation"],
Cell[5537, 183, 477, 13, 40, "Text"],
Cell[6017, 198, 87, 2, 43, "InputOnly"],
Cell[6107, 202, 1620, 55, 92, "Text"]
}, Open ]],
Cell[CellGroupData[{
Cell[7764, 262, 58, 0, 63, "Section"],
Cell[7825, 264, 110, 3, 24, "Text"],
Cell[CellGroupData[{
Cell[7960, 271, 101, 2, 42, "Input"],
Cell[8064, 275, 74, 2, 41, "Output"]
}, Open ]],
Cell[8153, 280, 71, 2, 43, "InputOnly"],
Cell[CellGroupData[{
Cell[8249, 286, 67, 2, 42, "Input"],
Cell[8319, 290, 529, 7, 112, "Print"]
}, Open ]],
Cell[8863, 300, 520, 15, 72, "Text"],
Cell[9386, 317, 683, 18, 91, "InputOnly"],
Cell[CellGroupData[{
Cell[10094, 339, 82, 2, 42, "Input"],
Cell[10179, 343, 123, 3, 41, "Output"]
}, Open ]],
Cell[10317, 349, 88, 3, 40, "Text"]
}, Open ]],
Cell[CellGroupData[{
Cell[10442, 357, 41, 0, 63, "Section"],
Cell[10486, 359, 738, 11, 104, "Text"],
Cell[CellGroupData[{
Cell[11249, 374, 95, 1, 42, "Subsubsection"],
Cell[11347, 377, 838, 21, 88, "Program"]
}, Open ]]
}, Open ]],
Cell[CellGroupData[{
Cell[12234, 404, 28, 0, 63, "Section"],
Cell[12265, 406, 135, 3, 24, "Text"]
}, Open ]]
}, Open ]]
}
]
*)
(***********************************************************************
End of Mathematica Notebook file.
***********************************************************************)