Delayed column generation example
Task and strategy
We are to transport a set of unsplittable items using the minimum
number of camels. Items have value and weight, and
each camel can carry items of at most 200 units of value, and at
most 100 units of weight in total. There exist 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. Well, we can't change the demands.
Instead, we 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: To find a good new pattern, we value each item type
according to the shadow price of its corresponding demand
constraint. We fit highly-priced items into a new pattern, subject
to the value and weight constraints. Having obtained a new
pattern, we introduce a new use(.) variable for it, solve
again, look at the shadow prices etc.
If the knapsack's value is 1, we stop. This is because the initial
patterns, regarded as "knapsacks" as above, all have 1 unit of
total value when weighted according to the shadow price of the
single item type they contain, and we want to prevent looping over the
same patterns. Note though that this simplistic strategy may cause
us to miss patterns that are required to build the optimum solution.
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: v3.pl (solution: sol3.txt)
15 item types: v15.pl (solution: sol15.txt)
21 item types: v21.pl (solution: sol21.txt)
25 item types: v25.pl (solution: sol25.txt)
The Prolog program is camels.pl.
Tested with SWI-Prolog 7.3.11.
The Mosel solution as I handed it in back then is
kamele.mos. 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 optimum solutions in all cases.
Related material: Stefan Kral's Prolog implementation of
a genetic algorithm for bin-packing is available
as binpack5.pl (adapted for
SWI Prolog). Example data:
implementations of first-fit, best-fit and worst-fit decreasing
heuristics are available
Written Dec 13th 2005
Keywords: Dantzig-Wolfe decomposition, LP relaxation, branch-and-price, column generation
Related: Combinatorial Optimization