# How to improve a column generation algorithm

I have been busy the last few weeks implementing this model with Column Generation in Gurobi and then solving it. The whole thing is now working quite well and I have also run a few calculation studies and noticed the following. It should be noted that I did the whole thing for a more complex model than shown in the post. I noticed two things.

1. In about 65% of the cases, the model delivers an optimal solution. The optimality gap of the non-optimal solutions is about 2% on average.
2. The runtime improvements are sometimes very high. In some cases, a model instance that can be solved with the normal solver in one hour can be solved in less than one minute. The median of the time improvements is about a 20-fold time improvement.

Now to my question. How can the algorithm be improved, especially with regard to the optimality gap, without having to implement branch-n-price? Are there other ways to improve the runtime? In this context, I noticed in my computational study that, as with all other column generation approaches, convergence is very slow at the higher iterations (I add columns in my model where the reduced cost is $$<10^{-6}$$).

I initially thought of dual price smoothing as a way out. In this context, I noticed that the non-negative dual values $$\pi_{ds}$$ fluctuate greatly. They are either exactly $$0$$ or very close to $$\sim 1$$ or exactly $$1$$, but never anything in between. The unrestricted dual values $$\mu_i$$ are also subject to strong fluctuations, whereby they become more and more negative with each iteration. Based on this, I now use these smoothed dual values: \begin{align} &\hat{\pi}_{ds}^t = (1-\alpha_1) \pi_{ds}^t +\alpha_1 \hat{\pi}_{ds}^{t-1}\label{smooth1}\\ &\hat{\mu}_i^t = (1-\alpha_2) \mu_i^t + \alpha_2 \hat{\mu}_i^{t-1}\label{smooth2} \end{align} Which of course also changes the objective function of the subproblems $$\mathcal{SP}(i)$$ accordingly. Unfortunately, I don't know exactly how to parameterise $$\alpha_{1,2}$$. I have also thought about dual stabilisation, but there is also the problem of parameterisation. Are there any other possibilities that might be easier to implement (possibly without parameterisation) that would improve the calculation time but also the quality of the solution?

If you are interested in providing gurobi specific soutions I will gladly link my code.

• How do you currently find integer feasible solutions? Mar 16 at 8:37
• For $\lambda_{ir}$ yes, for $motivation_{its}$ not, which was to be expected as $motivation$ is continous. Mar 16 at 10:04
• Instead of manually smoothing, you might try using an interior point algorithm (without crossover) for the master solves. Mar 16 at 11:12
• @RobPratt Can you provide a bit more information on how to implement it and it's benefits? Mar 16 at 22:41
• Check the manual for the LP solver options. It might be called “barrier” instead of interior point. You should naturally see less dual fluctuation. Mar 16 at 23:58