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
sub-problem: 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.
Prolog solution
As a lab assignment, we implemented the algorithm using
the Mosel programming
language.
Here, I am providing a solution that is implemented
in Prolog,
using library(simplex)
that ships with Scryer Prolog.
The Prolog version is much slower than the Mosel version, due to
my very simplistic simplex and branch and bound implementations. I
plan to improve library(simplex) in the future. 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 Scryer Prolog 0.9.0.
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, you can test the Prolog code interactively, and
reason about it declaratively.
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 (value2 + weight2), i.e., 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
Scryer Prolog). Example data:
dataset.pl. Prolog
implementations of first-fit, best-fit and worst-fit decreasing
heuristics are available
as knap.pl.
Written Dec 13th 2005
Keywords: Dantzig-Wolfe decomposition, LP relaxation, branch-and-price, column generation
Related: Combinatorial Optimization
Main page