# 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 (*value*^{2} + *weight*^{2}), 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**