We are to transport a set of unsplittable items using a minimal
number of camels. Items have value and weight, and each camel can
carry items worth at most 200 units, and weighing at most
100 units in total. There exist (integral) demands for each
type of item that we need to satisfy.
This optimization problem (bin packing) can be formulated
as an integer linear program in a straight-forward way. However,
the naive formulation won't do since the number of possible
packing patterns is typically infeasibly large. Therefore, we
will first generate packing patterns that look promising and then
determine the optimal solution possible using only those.
The initial set of patterns consists of one pattern for each item
type, taking as many items of that type as fit on one camel.
To find better patterns, we introduce variables use(i)
that denote how many times to apply pattern i (i.e.,
how many camels to pack according to that pattern), and let the
objective function be the sum over
these use(i). Minimize that sum (= number of camels)
with respect to the relaxed linear program. Then, look at
the shadow price of each demand-constraint: Informally, the shadow
price tells you how many camels we could spare if the
corresponding demand were one unit less than it is. Well, we can't
change the demands. Instead, we'll generate an additional pattern
consisting of items with high shadow prices, in the hope that
their being available in more patterns helps to spare camels in
subsequent iterations. We thus have to solve an
integer knapsack problem as a side-effect: The shadow
prices of demand constraints are regarded as values of the
respective item types that we want to fit into a pattern subject
to the value/weight constraints. Having obtained a new pattern,
we introduce a use(.) variable for it, solve again, look
at the shadow prices etc.
If the knapsack's value is 1, we can stop, because sparing exactly
one camel if the demand decreases by one doesn't buy us anything -
we can do that by decreasing the usage of the corresponding
initial pattern already.
In the last step, all use(i) variables are constrained to
integral values, and the problem is solved using the initial and
generated patterns.
As a lab assignment, we implemented the algorithm using the Mosel
programming language. The Prolog version is slow in comparison due
to my comparatively simplistic simplex and branch and bound
implementations. Here are some problem files and solutions (the
i-th number in the "vector" line denotes how many times to apply
the i-th pattern - you can also see that the first lines contain
the diagonal matrix of trivial patterns that consist of only one
item type each):
3 item types (solution)
15 item types (solution)
21 item types (solution)
25 item types (solution)
The Prolog program is here (tested with
SWI-Prolog 5.5.38 on a Pentium 2.4 GHz).
The Mosel solution as I handed it in back then is
here. In the Prolog version, rational
arithmetic obsoletes things like the eps constant. Also,
SWI-Prolog ships with a graphical tracer, and you can test the
Prolog code interactively.
An accompanying contest required solutions of problems with more
variables than the student version of Mosel could handle. One team
used a randomized algorithm to obtain incrementally better
solutions and scored third. Another team bought the commercial
version of Mosel and came in second. The winnig team used a
first-fit decreasing heuristics, sorting the items in decreasing
order of (value^2 + weight^2) (the squared "diagonal" of the two
constraint dimensions), with which they found
provably optimal solutions in all cases.
Related material: Stefan Kral's Prolog implementation of
a genetic algorithm for bin-packing is available
from here (adapted for
SWI Prolog). Example data
are here. Prolog
implementations of first-fit, best-fit and worst-fit decreasing
heuristics are available
from here.
Written Dec 13th 2005
Keywords: Dantzig-Wolfe decomposition, LP relaxation, branch-and-price, column generation
Main page