Why is the tailing off effect only a problem in column generation?

Question

Why is the tailing off effect only a problem in column generation? If all columns were pregenerated, and one used the simplex method, wouldn't one see the tailing off effect? Is it simply not an issue because each iteration is so quick that it does not matter?

If one made a figure with simplex iteration on the x-axis and objective function improvement on the y-axis, would the graph be a concave funtion converging towards 0? Wouldn't this be the same as the tailing off effect?

Answer 1

"Tailing-off effect" is a generic term that refers to an something like "the algorithm is hitting a plateau and progress becomes very slow towards the end". In other words: after some rapid progress in the beginning, the bulk of subsequent iterations only marginally improve the quality of your solution.

It is not found only in column generation, but in virtually any and all optimization algorithms, whether it's gradient descent, simplex, Benders decomposition, etc.

[some column generation-specific remarks are below]

Here is an example for the simplex algorithm. The following graphs show the progress made by Gurobi's dual simplex algorithm on the braun instance from H. Mittelmann's LP simplex benchmark.

You can see that, after about 750,000 iterations, the progress is much much slower when looking at the improvement in objective value. This could be referred to as tailing-off. This same behavior can be visualized by plotting the relative objective gap over the iterations:

Here I defined the relative objective gap as $gap = \frac{|z_{k} - z^{*}|}{|z^{*}|}$, where $z_{k}$ is the objective value at iteration $k$, and $z^{*}$ is the optimal objective value. Again, the gap barely improves after 750,000 iterations, and the subsequent iterations account for 25% of the total number of iterations.

However, just because we don't have any visible improvement, doesn't mean there's none. Indeed, let's look at the relative gap in logarithmic scale:

Now the observation is reversed: the relative gap is decreased by 2 orders of magnitude in the first 750,000 iterations, and but 4 orders of magnitude in the last 250,000.

The main point is that, even though we, as humans, don't see much improvement towards the end, progress is still being made. We're just not always looking at the right metric / scaling.

---

A few column generation-specific remarks

• Tailing-off can be observed on both the primal side (solution objective value) and the dual side (dual bound).
• It is also possible to see that either bound does not improve for a while, especially towards the end of the algorithm. This is often a combined effect of degeneracy and oscillation in the dual variables.
• One can look at the excellent Column Generation book by G. Desaulniers (especially the first and last chapters) for more in-depth discussion.