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: (solution: sol3.txt)
15 item types: (solution: sol15.txt)
21 item types: (solution: sol21.txt)
25 item types: (solution: sol25.txt)

The Prolog program is 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 (adapted for Scryer Prolog). Example data: Prolog implementations of first-fit, best-fit and worst-fit decreasing heuristics are available as

Written Dec 13th 2005
Keywords: Dantzig-Wolfe decomposition, LP relaxation, branch-and-price, column generation

Related: Combinatorial Optimization

Main page