Column Generation Flashcards
Assumptions for the Cutting Stock Problem (CSP)
metalworking company produces steel rods which can be cut in various sizes
it is easier to produce steel rods i of equal size w first and then cut them into smaller pieces j of a certain length l_j <= w.
the demand d_j has to be satisfied for each final j
unavoidably, the cutting process will produce waste
goal is to minimize the waste or, equivalently, reduce the numbers of steel rods i that are used
Thoughts on the direct model formulation for the CSP
Disadvantages:
l! symmetric solutions, which make the problem extremely hard to solve with Branch&Bound.
Valid (but poor) upper bound for the maximum number of steel rods I to be considered can be acquired through sum(j, d_j).
Huge number of integer and binary variables.
CSP reformulation idea
Instead of focussing on which steel rod a particular part is to be cut from, we look at possible cutting patterns like
a_k = (2, 0, 1)^T where a_1k = 2 means, that 2 finals of length l_1 are included in cutting pattern k…
How many times should a particular cutting pattern be used?
How many feasible cutting patterns are there?
In general: Exponentially many cutting patterns.
It is not possible to construct all cutting patterns (due to computational effort and memory constraints)
When is a cutting pattern efficient?
If they waste less steel rods than other cutting papers, meaning if the left-over waste in a particular steel rod is < min(l_j)
(heißt einfach nur, dass in das Überbleibsel kein weiterer “Finalstab” mehr reinpassen würden)
Why is it neither useful nor necessary to generate all efficient cutting patterns in advance and how can this problem be tackled?
Focussing on constructing efficient cutting patterns also requires numerical effort due to the exponentially increasing number of cutting patterns.
Therefore the idea is to generate “beneficial” cutting patterns on demand (by a column generation approach), which limits the amount of cutting patterns.
Formula for the reduced costs of a primal variable x_j
r_j = c_j - sum(i, a_(i,j)*pi_i)
If at least one of the reduced costs from your problem is > 0, then the solution is not yet optimal
(because by producing more of them or switching usages, you could save more money there :^))
