2
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ After posting this answer, I realised that Rob Pratt suggested the same thing in a comment. I definitely second this suggestion. $\endgroup$ Mar 17 at 5:06
  • $\begingroup$ Thank you for your answer. Can you maybe provide any paper that uses such a technique? $\endgroup$ Mar 18 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.