2

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.

Alberto Santini
  • 2,113
  • 9
  • 23
nflgreaternba
  • 99
  • 1
  • 8
  • 1
    How do you currently find integer feasible solutions? – fontanf Mar 16 '24 at 08:37
  • For $\lambda_{ir}$ yes, for $motivation_{its}$ not, which was to be expected as $motivation$ is continous. – nflgreaternba Mar 16 '24 at 10:04
  • 1
    Instead of manually smoothing, you might try using an interior point algorithm (without crossover) for the master solves. – RobPratt Mar 16 '24 at 11:12
  • @RobPratt Can you provide a bit more information on how to implement it and it's benefits? – nflgreaternba Mar 16 '24 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. – RobPratt Mar 16 '24 at 23:58
  • @nflgreaternba my question was not whether but how – fontanf Mar 17 '24 at 08:14
  • @fontanf Sorry, I must have misread it. After no more promising columns are found, I restore the integrality for $\lambda$. Thus it only finds integers for $\lambda$, and since the sum of all $\lambda$ needs to be equal to 1, I only get one final roster per index $i$. – nflgreaternba Mar 17 '24 at 09:33
  • I think it depends a bit on where the bottleneck is. You want a smaller optimality gap (don't we all?), which means you have two options: either improve the lower bound from the relaxation or improve the upper bound obtained from feasible solutions. You need to analyse whether your lower bound or your upper bound is the problem. – Sune Mar 19 '24 at 07:51
  • @Sune Thank you for your comment. How would I determine if one or the other is the problem? – nflgreaternba Mar 19 '24 at 08:51
  • One way to check if your upper bound is the culprit is to employ a (good) heuristic. If your price and branch algorithm returns a solution, you may use that as a starting solution for a local search heuristic. If you are able to improve on the solution, the large gap can be explained by too bad solutions from the generated columns. – Sune Mar 19 '24 at 16:27

1 Answers1

2

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

Alberto Santini
  • 2,113
  • 9
  • 23