How to improve a column generation algorithm

Question

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.

Answer 1

An extremely simple thing that has worked for me in the past is the following. Instead of implementing dual stabilisation explicitly, change a single solver parameter: use the Barrier instead of the Simplex algorithm when solving the reduced relaxed master problem. When applied to the dual, it makes it much more likely that the optimal dual solution lies midface rather than on a vertex, performing some implicit dual stabilisation. Depending on the solver you use, you might also have to disable the crossover procedure explicitly. I cannot guarantee it works in all cases, but it takes no effort to implement, and, in a paper I am working on, it reduced the runtime from ~4600 seconds to 52 seconds on a class of instances. (On other classes, the improvements were more modest.)