% Problem set 1: solutions
% Combinatorial Optimization, SUAMI, summer 2015
% Brian Kell
\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=9truein
\pdfhorigin=1.5truein \pdfvorigin=1truein
\font\titlefont=cmbx12
\def\transpose{{\rm T}}
\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
\bigbreak\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent{\bf Solution.}\enspace\ignorespaces}
% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
\parfillskip=0pt \finalhyphendemerits=0 \par}}
\def\subqed{{\unskip\nobreak\hfil\penalty50
\hskip1em\hbox{}\nobreak\hfil\raise2pt\hbox{\vrule height4pt width4pt depth0pt}
\parfillskip=0pt \finalhyphendemerits=0 \par}}
% pdfTeX graphics inclusion
% Examples: \pdftexfig{}{image.png} \pdftexfig{width3in}{figure.pdf}
\def\pdftexfig#1#2{\pdfximage#1{#2}\pdfrefximage\pdflastximage\relax}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~1: solutions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Formulate a linear program for the following optimization problem.
Then solve your linear program with Maple and interpret the results.
{\medskip\narrower
\noindent The Ace Refining Company produces two types of unleaded gasoline,
regular and premium, which it sells to its chain of service stations for
\$36~and~\$42 per barrel, respectively. Both types are blended from Ace's
inventories of refined domestic and refined foreign oil and must meet the
following specifications:
$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&&Maximum&Minimum&Maximum&Minimum\cr
&&vapor&octane&demand,&deliveries,\cr
&&pressure&rating&bbl/wk&bbl/wk\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
Regular&&23&88&100,000&50,000\cr
Premium&&23&93&\phantom020,000&\phantom05,000\cr}}$$
The characteristics of the refined oils in inventory are:
$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&&Vapor&Octane&Inventory,&Cost,\cr
&&pressure&rating&bbl&\$/bbl\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
Domestic&&25&87&40,000&16\cr
Foreign&&15&98&60,000&30\cr}}$$
What quantities of the two oils should Ace blend into the two gasolines in
order to maximize weekly profit? (Assume that vapor pressure and octane ratings
combine linearly in a blend.)
\medbreak}
{
\def\DR{\mathchoice{{\it DR}}{{\it DR}}{DR}{DR}}
\def\FR{\mathchoice{{\it FR}}{{\it FR}}{FR}{FR}}
\def\DP{\mathchoice{{\it DP}}{{\it DP}}{DP}{DP}}
\def\FP{\mathchoice{{\it FP}}{{\it FP}}{FP}{FP}}
\solution Let $\DR$~and~$\FR$ denote the numbers of barrels of domestic and
foreign oils, respectively, to be blended into regular gasoline per week, and
let $\DP$~and~$\FP$ denote the numbers of barrels of domestic and foreign oils,
respectively, to be blended into premium gasoline per week. (One nice thing
about linear programming is that since everything is linear we can have
multicharacter variable names without ambiguity, because variables are never
multiplied together in a linear program.) All of these variables are
nonnegative.
Ace's weekly profit is given by
$$(36-16)\DR+(36-30)\FR+(42-16)\DP+(42-30)\FP=20\DR+6\FR+26\DP+12\FP.$$
This is the objective function; the objective is to maximize this value.
Under the assumption that vapor pressure combines linearly in a blend, the
vapor pressure of the resulting regular gasoline will be
$(25\DR+15\FR)/(\DR+\FR)$, so to meet the maximum vapor pressure constraint for
regular gasoline we need
$${25\DR+15\FR\over\DR+\FR}\le23.$$
As written, this constraint is not linear. But we can multiply both sides by
$\DR+\FR$ to get $25\DR+15\FR\le23\DR+23\FR$, or $2\DR-8\FR\le0$. Likewise, the
maximum vapor pressure constraint for premium gasoline can be expressed as
$2\DP-8\FP\le0$.
Similarly, the minimum octane rating constraints for regular and premium
gasoline, respectively, are
$${87\DR+98\FR\over\DR+\FR}\ge88\qquad\hbox{and}\qquad
{87\DP+98\FP\over\DP+\FP}\ge93.$$
When written as linear constraints, these become $-\DR+10\FR\ge0$ and
$-6\DP+5\FP\ge0$.
\goodbreak
After including constraints for maximum demand, minimum deliveries, and
inventory, we get the following linear program.
$$\eqalignno{
{\rm maximize}\quad20\DR+\phantom06\FR+26\DP+12\FP&&\hbox{[weekly profit]}\cr
{\rm subject\ to}\quad\phantom02\DR-\phantom08\FR\phantom{{}+00\DP+00\FP}
&\le\phantom{000{,}00}0\qquad\qquad\qquad\qquad\qquad
&\hbox{[vapor pressure, regular]}\cr
2\DP-\phantom08\FP&\le\phantom{000{,}00}0&\hbox{[vapor pressure, premium]}\cr
-\DR+10\FR\phantom{{}+00\DP+00\FP}&\ge\phantom{000{,}00}0
&\hbox{[octane rating, regular]}\cr
-6\DP+\phantom05\FP&\ge\phantom{000{,}00}0&\hbox{[octane rating, premium]}\cr
\DR+\phantom{01}\FR\phantom{{}+00\DP+00\FP}&\le100{,}000
&\hbox{[max.\ demand, regular]}\cr
\DR+\phantom{01}\FR\phantom{{}+00\DP+00\FP}&\ge\phantom050{,}000
&\hbox{[min.\ deliveries, regular]}\cr
\DP+\phantom{01}\FP&\le\phantom020{,}000&\hbox{[max.\ demand, premium]}\cr
\DP+\phantom{01}\FP&\ge\phantom{00}5{,}000&\hbox{[min.\ deliveries, premium]}\cr
\DR\phantom{{}+00\FR}+\phantom{01}\DP\phantom{{}+00\FP}&\le\phantom040{,}000
&\hbox{[inventory, domestic]}\cr
\FR\phantom{{}+00\DP}+\phantom{01}\FP&\le\phantom060{,}000
&\hbox{[inventory, foreign]}\cr
&\phantom{{}=000{,}000}
\llap{$\DR\ge0$,\quad$\FR\ge0$,\quad$\DP\ge0$,\quad$\FP\ge0$}.\cr
}$$
\goodbreak
\noindent The following Maple worksheet can be used to solve this linear
program.
{\smallskip
\raggedright \advance\hsize by-2\parindent \hangindent=\parindent \tt
> restart;\hfil\break
> with(Optimization);
$$\displaylines{
[\it ImportMPS,Interactive,LPSolve,LSSolve,Maximize,Minimize,NLPSolve,\hfill\cr
\qquad\it QPSolve]\hfill\cr
}$$
> f:=(DR,FR,DP,FP)->20*DR+6*FR+26*DP+12*FP;
$$f:=(\DR,\FR,\DP,\FP)\to20\DR+6\FR+26\DP+12\FP$$
> constraints:=[2*DR-8*FR<=0,2*DP-8*FP<=0,-DR+10*FR>=0,\hfil\break
\strut\qquad-6*DP+5*FP>=0,DR+FR<=100000,DR+FR>=50000,DP+FP<=20000,\hfil\break
\strut\qquad DP+FP>=5000,DR+DP<=40000,FR+FP<=60000];
$$\displaylines{
{\it constraints}:=[2\DR-8\FR\le0,2\DP-8\FP\le0,0\le-\DR+10\FR,\hfill\cr
\qquad0\le-6\DP+5\FP,\DR+\FR\le100000,50000\le\DR+\FR,\hfill\cr
\qquad\DP+\FP\le20000,5000\le\DP+\FP,\DR+\DP\le40000,\FR+\FP\le60000]\hfill\cr
}$$
> LPSolve(f(DR,FR,DP,FP),constraints,'maximize',\hfil\break
\strut\qquad assume=nonnegative);
$$\displaylines{
\bigl[1.280000\;10^6,[\DP=9090.90909090919,\DR=30909.0909090908,\hfill\cr
\qquad\FP=10909.0909090908,\FR=49090.9090909092]\bigr]\hfill\cr
}$$
}
\noindent Therefore, an optimal solution is to blend approximately 30,909
gallons of domestic oil and 49,091 gallons of foreign oil to produce regular
gasoline, and to blend approximately 9,091 gallons of domestic oil and 10,909
gallons of foreign oil to produce premium gasoline; this will produce a profit
of \$1,280,000. (The exact values of the variables in this solution are
$\DR=340{,}000/11$, $\FR=540{,}000/11$, $\DP=100{,}000/11$, and
$\FP=120{,}000/11$.)
This is not the only optimal solution. There is another optimal basic feasible
solution, which is $\DR=40{,}000$, $\FR=40{,}000$, $\DP=0$, and $\FP=20{,}000$.
This solution also yields a profit of \$1,280,000. (And any convex combination
of these two solutions is also an optimal feasible solution.) \qed
} % end \def\DR, \def\FR, \def\DP, \def\FP
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Formulate a linear program for the following optimization problem.
Carefully draw the feasible region (i.e., the set of feasible solutions). Solve
the linear program graphically. Draw at least three level curves of the
objective function, including the level curve corresponding to the optimal
value.
{\medskip\narrower
\noindent A kennel owner has a choice of two dog foods to buy in bulk
quantities to feed the dogs under her care. The average dog in her kennel needs
at least 36~grams of protein, 12~grams of fat, and 9~milligrams of iron a day.
An ounce of Dog Grub includes 3~grams of protein, 1.5~grams of fat, and
0.5~milligrams of iron. An ounce of Canine Chow includes 2~grams of protein,
0.5~grams of fat, and 0.75~milligrams of iron. If Dog Grub and Canine Chow cost
\$0.12~and~\$0.15 per ounce, respectively, how much of each should she buy to
meet the daily needs of the average dog at a minimum cost?
}
\solution Let $d$~and~$c$ denote the number of ounces of Dog Grub and Canine
Chow, respectively, to be bought. Then the following linear program minimizes
the total cost subject to the nutritional requirements.
$$\eqalignno{
{\rm minimize}\quad0.12d+0.15c&&\hbox{[cost]}\cr
{\rm subject\ to}\quad3\phantom{.00}d+2\phantom{.00}c&\ge36&\hbox{[protein]}\cr
1.5\phantom0d+0.5\phantom0c&\ge12&\hbox{[fat]}\cr
0.5\phantom0d+0.75c&\ge\phantom09&\hbox{[iron]}\cr
&\phantom{{}=00}\llap{$d\ge0$,\quad$c\ge0$}.\cr
}$$
\noindent The feasible region is shaded in the figure below. It has four
corners: $(0,24)$, $(4,12)$, $(7.2,7.2)$, and $(18,0)$.
$$\pdftexfig{width4.5in}{pset01-2.pdf}$$
\goodbreak
\noindent To solve this linear program graphically, we evaluate the objective
function at each of these corners:
$$\vbox{\offinterlineskip
\halign{&\quad\hfil\strut#\hfil\quad&\vrule#\cr
Corner $(d,c)$&&Objective value\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$(0,24)$&&3.60\phantom0\cr
$(4,12)$&&2.28\phantom0\cr
$(7.2,7.2)$&&1.944\cr
$(18,0)$&&2.16\phantom0\cr}}$$
Since this is a minimizing linear program, we choose the smallest of these
objective values. Therefore, the optimal solution is $d=7.2$, $c=7.2$, having
an objective value of~1.944. In other words, the kennel owner should buy
7.2~ounces of both Dog Grub and Canine Chow for each dog each day, at a total
cost of just over \$1.94.
The figure above also shows three level curves of the objective function,
corresponding to the objective values 1.50,~1.944, and~2.50. Note that these
level curves are parallel lines. The level curve $0.12d+0.15c=1.50$ does not
pass through the feasible region, indicating that the objective value~1.50
cannot be attained. The level curve $0.12d+0.15c=2.50$ does pass through the
feasible region, but 2.50 is not the optimal objective value because level
curves corresponding to smaller objective values also pass through the feasible
region. The level curve $0.12d+0.15c=1.944$ corresponds to the optimal
objective value; it intersects the feasible region at exactly one point, which
is the corner $(7.2,7.2)$. From the level curves, we see that the objective
function decreases as we move down and to the left, so we can conclude that
the linear program does have an optimal solution even though the feasible
region is unbounded. \qed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Give a (simple) example of each of the following:
\smallskip
\item{(a)} An infeasible linear program.
\item{(b)} An unbounded linear program (i.e., a linear program with an
unbounded objective value).
\item{(c)} A linear program with a unique optimal solution.
\item{(d)} A linear program with a nonunique optimal solution.
\item{(e)} A linear program with an unbounded feasible region that does
{\it not\/} have an unbounded objective value.
\solution
\smallskip
\item{(a)} Here is an example of an infeasible linear program:
$$\eqalign{
{\rm maximize}\quad x&\cr
{\rm subject\ to}\quad x&\le-1\cr
x&\ge\phantom+0.\cr
}$$
\goodbreak
\item{(b)} Here is an unbounded linear program:
$$\eqalign{
{\rm maximize}\quad x&\cr
x&\ge0.\cr
}$$
(Note that the set of constraints here happens to be empty. The inequality
$x\ge0$ is a variable domain, not a constraint.)
\smallbreak
\item{(c)} The following linear program has a unique optimal solution:
$$\eqalign{
{\rm maximize}\quad x\cr
{\rm subject\ to}\quad x&\le1\cr
x&\ge0.\cr
}$$
The unique optimal solution is $x=1$.
\smallbreak
\item{(d)} The following linear program has a nonunique optimal solution:
$$\eqalign{
{\rm maximize}\quad x+y\cr
{\rm subject\ to}\quad x+y&\le1\cr
x\ge0,\quad y&\ge0.\cr
}$$
The optimal objective value,~1, is achieved at all points on the line segment
joining $(0,1)$ and $(1,0)$.
\smallbreak
\item{(e)} Here is a linear program with an unbounded feasible region that does
not have an unbounded objective value:
$$\eqalign{
{\rm minimize}\quad x+y&\cr
x\ge0,\quad y\ge0&.\cr
}$$
The feasible region is the entire first quadrant, which is an unbounded region,
but the optimal objective value is~0, so the {\it linear program\/} is not
unbounded. (For another example, see Problem~2.) \qed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem A {\it convex combination\/} of two vectors $x$~and~$x'$ (of the same
size) is a vector of the form $\lambda x+(1-\lambda)x'$, where $\lambda$ is a
scalar in the interval $[0,1]$. Let $A=[a_{ij}]$ be an $m\times n$ matrix and
let $b=[b_1,\ldots,b_m]^\transpose$ be an $m\times1$ column vector. Consider
the set of constraints $Ax\le b$, where $x$ is an $n\times1$ column vector.
(The inequality $Ax\le b$ means that each coordinate of~$Ax$ is less than or
equal to the corresponding coordinate of~$b$; so it is a set of
$m$~inequalities.) Suppose that $x=[x_1,\ldots,x_n]^\transpose$ and
$x'=[x'_1,\ldots,x'_n]^\transpose$ are both feasible solutions to this set of
constraints. Prove that any convex combination of $x$~and~$x'$ is also
feasible.
\solution Let $\lambda\in[0,1]$. Since $x$~and~$x'$ are both feasible solutions
to this set of constraints, we know $Ax\le b$ and $Ax'\le b$, so $Ax-b\le0$ and
$Ax'-b\le0$. Therefore
$$\eqalign{
A[\lambda x+(1-\lambda)x']-b
&=\lambda Ax+(1-\lambda)Ax'-\lambda b-(1-\lambda)b\cr
&=\underbrace{\vphantom(\lambda}_{\ge0}\underbrace{(Ax-b)}_{\le0}
+\underbrace{(1-\lambda)}_{\ge0}\underbrace{(Ax'-b)}_{\le0}\cr
&\le0.\cr
}$$
Hence $A[\lambda x+(1-\lambda)x']\le b$, which is to say,
$\lambda x+(1-\lambda)x'$ is feasible. \qed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Here is another example of a combinatorial optimization problem. We
have not yet discussed methods for solving problems like this, but see if you
can find a good approach. Your goal is to find the optimal solution to the
problem and to {\it prove\/} that it is optimal.
{\medskip\narrower
\noindent Indiana Jones has made it through the deadly traps of an ancient
temple and has discovered ten treasures inside. Unfortunately, his knapsack is
too small to carry them all, so he must choose (wisely). He has made the
following estimates of the objects' weights and values. If his knapsack can
hold at most 20~pounds of treasure, which objects should he take to maximize
the value of his loot?
$$\hss\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\quad&&\hfil\strut#\quad\cr
Treasure&&Weight&Value\cr
\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit\cr
Crown of Atahualpa&&4 lb.&\$\phantom04,000\cr
Itzcoatl's Orb&&6 lb.&9,000\cr
Tablet of the Heavens&&7 lb.&7,000\cr
Golden Quetzal&&13 lb.&17,000\cr
Mask of the Ancients&&5 lb.&5,000\cr
}}\qquad\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\quad&&\hfil\strut#\quad\cr
Treasure&&Weight&Value\cr
\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit\cr
Key of Silver Light&&2 lb.&\$\phantom02,000\cr
Idol of Inti&&10 lb.&15,000\cr
Eternal Quipu&&5 lb.&8,000\cr
Goblet of Uxmal&&3 lb.&4,000\cr
Sacred Stone of Cuzco&&8 lb.&11,000\cr
}}\hss$$
}
\solution We might first try sorting the objects by value, and then choosing
the highest-value items one by one, so long as we still have room in the
knapsack. First we sort the treasures in descending order by value. (We'll put
the Goblet of Uxmal ahead of the Crown of Atahualpa, because they are have the
same value but the goblet weighs less.)
$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\quad&&\hfil\strut#\quad\cr
Treasure&&Weight&Value\cr
\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit\cr
Golden Quetzal&&13 lb.&\$17,000\cr
Idol of Inti&&10 lb.&15,000\cr
Sacred Stone of Cuzco&&8 lb.&11,000\cr
Itzcoatl's Orb&&6 lb.&9,000\cr
Eternal Quipu&&5 lb.&8,000\cr
Tablet of the Heavens&&7 lb.&7,000\cr
Mask of the Ancients&&5 lb.&5,000\cr
Goblet of Uxmal&&3 lb.&4,000\cr
Crown of Atahualpa&&4 lb.&4,000\cr
Key of Silver Light&&2 lb.&2,000\cr
}}$$
Now let's fill the knapsack. We'll take the Golden Quetzal, since it has the
highest value. Since the Golden Quetzal weighs 13~pounds, we have 7~pounds of
capacity left. We cannot take either of the next two items in the list, the
Idol of Inti or the Sacred Stone of Cuzco, because they weigh too much. So
we'll take Itzcoatl's Orb, which weighs 6~pounds. This gives us 19~pounds,
worth~\$26,000. Since there is no 1-pound item, this is the best we can do by
this method. (Such a method, in which we simply take the ``best'' available
choice at each step without considering how our choice will affect future
options, is called a ``greedy algorithm.'')
But we can do better if we modify the method slightly. We weren't able to fill
our knapsack because there is no 1-pound item to take. So let's try the same
method, except that we will skip an item if it would give us a total of exactly
19~pounds. (We'll call this approach the ``modified greedy algorithm.'') As
before we take the Golden Quetzal and skip the Idol of Inti and the Sacred
Stone of Cuzco. This time we will also skip Itzcoatl's Orb and take the Eternal
Quipu instead, giving us 18~pounds so far. Then we still have room to take the
Key of Silver Light. This solution gives us a full 20~pounds of treasure
worth~\$27,000.
However, there is another way to sort the treasure. Instead of sorting by value
with no regard to weight, we can sort by value per pound. (As before, if two
objects have the same value per pound, let's put the lighter one first.)
Sorting the treasures in this way gives the following list.
$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\quad&\hfil\strut#\quad&\hfil\strut#\hfil\quad\cr
Treasure&&Weight&Value&Value per pound\cr
\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit\cr
Eternal Quipu&&5 lb.&\$\phantom08,000&\$1,600/lb.\cr
Itzcoatl's Orb&&6 lb.&9,000&\phantom\$1,500/lb.\cr
Idol of Inti&&10 lb.&15,000&\phantom\$1,500/lb.\cr
Sacred Stone of Cuzco&&8 lb.&11,000&\phantom\$1,375/lb.\cr
Goblet of Uxmal&&3 lb.&4,000&\phantom\$1,333/lb.\cr
Golden Quetzal&&13 lb.&17,000&\phantom\$1,308/lb.\cr
Key of Silver Light&&2 lb.&2,000&\phantom\$1,000/lb.\cr
Crown of Atahualpa&&4 lb.&4,000&\phantom\$1,000/lb.\cr
Mask of the Ancients&&5 lb.&5,000&\phantom\$1,000/lb.\cr
Tablet of the Heavens&&7 lb.&7,000&\phantom\$1,000/lb.\cr
}}$$
If we apply the greedy algorithm to this list, we begin by taking the Eternal
Quipu and Itzcoatl's Orb, bringing us to a total of 11~pounds. We do not have
enough room for the Idol of Inti, but we can take the Sacred Stone of Cuzco. We
must stop here, because we have reached 19~pounds; the value of our treasure
is~\$28,000.
This is an improvement upon the solutions we obtained earlier. Perhaps we can
improve even further if we try the modified greedy algorithm. We choose the
Eternal Quipu and Itzcoatl's Orb and skip the Idol of Inti, as before, but now
we skip the Sacred Stone of Cuzco as well, because that would give us a total
of 19~pounds. Instead we take the Goblet of Uxmal, the Key of Silver Light, and
the Crown of Atahualpa. We have filled our knapsack with 20~pounds, but when we
calculate the value it turns out that we have done worse; we have only
\$27,000.
The greedy algorithm and the modified greedy algorithm are simple methods to
use, and they usually work well to get an {\it approximation\/} of the best
solution, but neither of these methods is {\it guaranteed\/} to give the best
solution. In this problem there is a better solution than any of the four we
have found so far.
Let's go about this in a very systematic way. We have already found a solution
worth \$28,000. If we are going to improve upon this, we must include in our
solution at least one of the five highest-value items (the Golden Quetzal, the
Idol of Inti, the Sacred Stone of Cuzco, Itzcoatl's Orb, or the Eternal Quipu)
because the other five items are worth only \$22,000 in all. So we will
consider the five high-value items separately from the five low-value items.
The low-value items are listed below, sorted in ascending order by weight
(and, incidentally, also by value).
$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\quad&&\hfil\strut#\quad\cr
Treasure&&Weight&Value\cr
\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit\cr
Key of Silver Light&&2 lb.&\$2,000\cr
Goblet of Uxmal&&3 lb.&4,000\cr
Crown of Atahualpa&&4 lb.&4,000\cr
Mask of the Ancients&&5 lb.&5,000\cr
Tablet of the Heavens&&7 lb.&7,000\cr
}}$$
We will make a list of ways to form various weights from these low-value
treasures. It is easy to see that the only way to make 2~pounds is to take the
Key of Silver Light. Similarly, the only way to make 3~pounds is to take the
Goblet of Uxmal, and the only way to make 4~pounds is to take the Crown of
Atahualpa. To make 5~pounds, however, we have a choice: either we can take the
Mask of the Ancients alone, or we can take the Key of Silver Light and the
Goblet of Uxmal. In general, when our aim is to form a total weight of
$n$~pounds, we must also consider all of the possible ways to write $n$ as a
sum of smaller numbers (out of 2,~3, 4, 5, and~7). Following this approach, we
construct the ``low-value combinations'' table on the following page.
To use this table, we will consider some combination of the high-value
treasures, see how much room is left in the knapsack, and then find the best
combination of low-value treasures in the table above that will fit. For
example, if we choose the Sacred Stone of Cuzco and Itzcoatl's Orb as our
high-value treasures, which together weigh 14~pounds, we will have 6~pounds of
capacity remaining. Looking at the ``6~lb.''\ row and the rows above it in this
table, we see that our best option is to take the Key of Silver Light and the
Crown of Atahualpa (or, equivalently, the Key of Silver Light and the Goblet of
Uxmal---perhaps this is actually a better choice, since it gives us the same
value with less weight).
Proceeding in this way, we can find the best collection of treasures to take by
considering all possible combinations of the high-value items; see the
``high-value combinations'' table on the next page. Of course, we can safely
ignore those that put us overweight: the Golden Quetzal and the Idol of Inti
together weigh 23~pounds, and the Golden Quetzal and the Sacred Stone of Cuzco
together weigh 21~pounds. Furthermore, any combination of three or more
high-value items will weigh more than 20~pounds (except the three lightest
ones, the Sacred Stone of Cuzco, Itzcoatl's Orb, and the Eternal Quipu, which
weigh 19~pounds together). These impossible combinations of high-value items
are omitted from the table.
From these tables we see that the best choice is to take the Idol of Inti, the
Eternal Quipu, the Key of Silver Light, and the Goblet of Uxmal, which weigh
20~pounds together and have a total value of~\$29,000. Moreover, this solution
is unique.
(With the particular numbers used in this problem, it turns out that we would
have found this optimal solution by using the greedy algorithm based on value
per pound if we would have broken ties by putting the {\it heavier\/} item
first rather than the lighter one. But this isn't a general rule that will
always give the best possible solution.)
\vfill\eject
\centerline{\vbox{\offinterlineskip
\halign{\quad\hfil\strut#&\quad\hfil\strut#\hfil&\quad\strut#\hfil&\quad\hfil\strut#\quad\cr
\multispan4\hfil\bf Low-value combinations\hfil\cr
\noalign{\smallskip}
Weight&As a sum&Treasures&Value\cr
\noalign{\vskip1pt\hrule\vskip1pt}
2 lb.&2&Key&\$\phantom02,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
3 lb.&3&Goblet&4,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
4 lb.&4&Crown&4,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
5 lb.&5&Mask&5,000\cr
&$2+3$&Key, goblet&6,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
6 lb.&$2+4$&Key, crown&6,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
7 lb.&7&Tablet&7,000\cr
&$2+5$&Key, mask&7,000\cr
&$3+4$&Goblet, crown&8,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
8 lb.&$3+5$&Goblet, mask&9,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
9 lb.&$2+7$&Key, tablet&9,000\cr
&$4+5$&Crown, mask&9,000\cr
&$2+3+4$&Key, goblet, crown&10,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
10 lb.&$3+7$&Goblet, tablet&11,000\cr
&$2+3+5$&Key, goblet, mask&11,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
11 lb.&$4+7$&Crown, tablet&11,000\cr
&$2+4+5$&Key, crown, mask&11,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
12 lb.&$5+7$&Mask, tablet&12,000\cr
&$2+3+7$&Key, goblet, tablet&13,000\cr
&$3+4+5$&Goblet, crown, mask&13,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
13 lb.&$2+4+7$&Key, crown, tablet&13,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
14 lb.&$2+5+7$&Key, mask, tablet&14,000\cr
&$3+4+7$&Goblet, crown, tablet&15,000\cr
&$2+3+4+5$&Key, goblet, crown, mask&15,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
15 lb.&$3+5+7$&Goblet, mask, tablet&16,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
16 lb.&$4+5+7$&Crown, mask, tablet&16,000\cr
&$2+3+4+7$&Key, goblet, crown, tablet&17,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
17 lb.&$2+3+5+7$&Key, goblet, mask, tablet&18,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
18 lb.&$2+4+5+7$&Key, crown, mask, tablet&18,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
19 lb.&$3+4+5+7$&Goblet, crown, mask, tablet&19,000\cr
\noalign{\vskip1pt\hrule\vskip1pt}
21 lb.&$2+3+4+5+7$&Key, goblet, crown, mask, tablet&22,000\cr
}}}
\vfill
\centerline{\vbox{\offinterlineskip
\def\B{$\bullet$}
\halign{%
\quad\hfil\strut#\hfil&\quad\hfil\strut#\hfil&\quad\hfil\strut#\hfil
&\quad\hfil\strut#\hfil&\quad\hfil\strut#\hfil\quad&\vrule#%
&\quad\hfil\strut#&\quad\strut#\hfil&\quad\hfil\strut#\quad\cr
\multispan9\hfil\bf High-value combinations\hfil\cr
\noalign{\smallskip}
Quetzal&Idol&Stone&Orb&Quipu&&Remaining&Low-value items&\llap{Total value}\cr
\omit&\omit&\omit&\omit&\omit&height1pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&height1pt\cr
\B& & & & &&7 lb.&Goblet, crown&\$25,000\cr
&\B& & & &&10 lb.&Goblet, tablet&26,000\cr
& &\B& & &&12 lb.&Key, goblet, tablet&24,000\cr
& & &\B& &&14 lb.&Goblet, crown, tablet&24,000\cr
& & & &\B&&15 lb.&Goblet, mask, tablet&24,000\cr
\omit&\omit&\omit&\omit&\omit&height1pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&height1pt\cr
\B& & &\B& &&1 lb.&\it(None)&26,000\cr
\B& & & &\B&&2 lb.&Key&27,000\cr
&\B&\B& & &&2 lb.&Key&28,000\cr
&\B& &\B& &&4 lb.&Crown&28,000\cr
&\B& & &\B&&5 lb.&Key, goblet&29,000\cr
\omit&\omit&\omit&\omit&\omit&height1pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&height1pt\cr
& &\B&\B& &&6 lb.&Key, crown&26,000\cr
& &\B& &\B&&7 lb.&Goblet, crown&27,000\cr
& & &\B&\B&&9 lb.&Key, goblet, crown&27,000\cr
& &\B&\B&\B&&1 lb.&\it(None)&28,000\cr
}}}
\eject
Another approach is to formulate the problem as an {\it integer program}, which
is like a linear program except that one or more variables are required to have
integer values. We associate each treasure with a variable that is constrained
to have the value 0~or~1; the value~1 will mean that the treasure is to be
included in the knapsack, and the value~0 will mean that the treasure is to be
left behind.
$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil&\strut\hfil#\hfil\quad\cr
Treasure&Variable\cr
\noalign{\vskip2pt\hrule\vskip2pt}
Crown of Atahualpa&$c$\cr
Itzcoatl's Orb&$o$\cr
Tablet of the Heavens&$t$\cr
Golden Quetzal&$q$\cr
Mask of the Ancients&$m$\cr}}\qquad\vbox{\offinterlineskip
\halign{\quad\strut#\hfil&\strut\hfil#\hfil\quad\cr
Treasure&Variable\cr
\noalign{\vskip2pt\hrule\vskip2pt}
Key of Silver Light&$k$\cr
Idol of Inti&$i$\cr
Eternal Quipu&$e$\cr
Goblet of Uxmal&$g$\cr
Sacred Stone of Cuzco&$s$\cr}}$$
The following integer program maximizes the value of the items included in the
knapsack, subject to the constraint that the total weight of the included items
is less than 20~pounds, no item can be included more than once, and every item
must be included an integer number of times. (The objective function is written
in units of thousands of dollars to avoid a profusion of zeroes in the
coefficients.)
$$\eqalignno{
{\rm maximize}\quad4c+9o+7t+17q+5m+2k+15i+8e+4g+11s&&\hbox{[value]}\cr
{\rm subject\ to}\quad4c+6o+7t+13q+5m+2k+10i+5e+3g+\phantom08s&\le20\qquad
&\hbox{[weight]}\cr
c\phantom{{}+0o+0t+00q+0m+0k+00i+0e+0g+00s}&\le\phantom01\cr
o\phantom{{}+0t+00q+0m+0k+00i+0e+0g+00s}&\le\phantom01\cr
t\phantom{{}+00q+0m+0k+00i+0e+0g+00s}&\le\phantom01\cr
q\phantom{{}+0m+0k+00i+0e+0g+00s}&\le\phantom01\cr
m\phantom{{}+0k+00i+0e+0g+00s}&\le\phantom01\cr
k\phantom{{}+00i+0e+0g+00s}&\le\phantom01\cr
i\phantom{{}+0e+0g+00s}&\le\phantom01\cr
e\phantom{{}+0g+00s}&\le\phantom01\cr
g\phantom{{}+00s}&\le\phantom01\cr
s&\le\phantom01\cr
\setbox0=\hbox{$0c+0o+0t+00q+0m+0k+00i+0e+0g+0s$}
\hbox to\wd0{\hfil All variables nonnegative integers.\hfil}\cr
}$$
This integer program can be solved with Maple in the same way that a linear
program is solved, the only change being {\tt assume=nonnegint} in the
{\it LPSolve\/} call rather than the usual {\tt assume=nonnegative}.
(Alternatively, using {\tt assume=binary} constrains all variables to take
values in the set $\{0,1\}$, so if this option is used only the first
constraint in the integer program is necessary.) Maple finds the optimal
solution $c=0$, $o=0$, $t=0$, $q=0$, $m=0$, $k=1$, $i=1$, $e=1$, $g=1$, $s=0$,
which corresponds to the solution we laboriously found above. \qed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem The phrase ``combinatorial optimization'' is a mouthful. Come up with
a shorter way to say~it.
\solution My first instinct was to shorten the phrase to ``combo oppo,'' but
I'm not sure how to justify the shortening of ``optimization'' to ``oppo''
except that it kinda sounds like a half-rhyme to ``combo.'' ``Combination'' is
often shortened to ``combo,'' and ``optimization'' is sometimes shortened to
``opti,'' so ``combo opti'' might be defensible. Something about it seems
awkward, though. The straightforward abbreviation ``C.O.'' is not too bad.
``Com op'' (or the alternative spelling ``comb op'') was the most common
submitted suggestion; this sounds pretty good. I also liked the suggestion
``combi op.'' A couple of people suggested avoiding the long words altogether,
preferring simpler, more straightforward descriptions like ``searching for the
best solution.'' The most aggressive suggestion was ``combat optz,'' which is
indeed a subsequence of ``combinatorial optimization,'' but perhaps suggests a
more violent field of study. \qed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bye