2
$\begingroup$

I've been working on solving a stochastic vehicle routing problem using Benders' decomposition with CPLEX in C++. Initially, my implementation struggled with larger instances, but I've made significant progress by implementing enhancement strategies such as reformulation of the subproblems according to Fischetti et al. (2010) and partial Benders' decomposition as described by Crainic et al. (2021).

However, I've encountered a bottleneck in my approach. When using partial Benders' decomposition, the master problem becomes complex, leading to longer solve times of the CPLEX solver for each iteration of the master problem. On the other hand, if I don't use partial Benders' decomposition, the master problem lacks scenario information, resulting in a high number of feasibility cuts and iterations, until feasible solutions are found.

In general, the one with partial Benders' decomposition seems more promising though, having better performance so far. The only problem is, due to the exponential complexity of VRPs, it reaches a threshold where it needs 20–30 minutes to solve each master problem instead of seconds, like before.

I'm seeking advice on how to overcome this issue. Has anyone faced a similar problem? At this point, small improvements would be enough for our practical use case, since I am not far off the instance sizes that we aim to solve.

Since with partial Benders' decomposition, the solver taking too long to solve the master problem is the bottleneck, could maybe Gurobi work better? Or are there general methods to speed up the solver?

Fischetti et al. (2010): https://link.springer.com/article/10.1007/s10107-010-0365-7

Crainic et al. (2021): https://pubsonline.informs.org/doi/abs/10.1287/trsc.2020.1022

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Thanks for noticing, just changed that. $\endgroup$
    – Arctic_Skill
    Commented Mar 15 at 14:38
  • $\begingroup$ I assume your master problem is an LP. Are you doing "one tree" Benders (adding cuts in a callback during a single solve) or solving the LP from scratch each time? If the latter, are you adding the Benders cuts as ordinary constraints or lazy constraints? $\endgroup$
    – prubin ♦
    Commented Mar 15 at 16:18
  • $\begingroup$ My MP is an IP (binary decisions variables, like they come in a standard VRP setting, i.e. decision if a node is served by a vehicle or not, or if an edge is traversed by a vehicle or not). I do not use callbacks so far and I add constraints the ordinary way. I don’t resolve the MP from scratch though, I add the new cuts and then resolve the problem using the cplex.solve() command. Do you think I could achieve better performance using callbacks? I’ve heard about that method, but I’m not familiar with it yet. $\endgroup$
    – Arctic_Skill
    Commented Mar 16 at 19:56

1 Answer 1

Reset to default
1
$\begingroup$

Calling cplex.solve() after modifying the model restarts the solver from the root node. Using callbacks would allow you to modify the model and then pick up from where you left off, so long as the changes to the model did not alter the feasibility of previously found incumbents.

You can do Benders with either legacy or generic callbacks, but the newer generic callbacks are generally preferable (albeit a bit trickier to implement, due to thread safety concerns). I believe there's at least one Benders example shipping with CPLEX that uses callbacks, and I wrote a blog post quite a while back providing an example (including Java source code). Using generic callbacks allows CPLEX to continue to use dynamic search (disabled when using legacy callbacks), which typically helps.

If using the one tree approach (solve MP, solve subproblem, add cut(s), repeat), you might want to consider adding the Benders cuts as lazy constraints rather than standard constraints. It will allow CPLEX to set them aside if they have not been binding for a while, which might speed up the master solve if you are piling up zillions of cuts.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Thank you! Very helpful. I will look into it. So far, I've basically treated CPLEX as a black box solver, not really putting much time into researching exactly what it does. Looks like it is time to change that. $\endgroup$
    – Arctic_Skill
    Commented Mar 18 at 7:58
  • 1
    $\begingroup$ Changing the cuts to lazy constraints requires considerably less alteration of code (see the addLazyConstraints method in the IloCplex class) than does the one-tree approach, so you may want to try it first. The one-tree approach is, I suspect, more likely to provide significant gains in the time (but, as with all things MIP related, you never know until you try). $\endgroup$
    – prubin ♦
    Commented Mar 18 at 15:28
  • $\begingroup$ Thanks, I will keep it in mind. Will try out lazy constraints first! Very helpful from you, that you further explain it. Especially since getting into callbacks seems quite complicated at first glance. $\endgroup$
    – Arctic_Skill
    Commented Mar 19 at 14:00
  • $\begingroup$ I just changed the addition of cuts so that they will all be added as lazy constraints. On first tests, I now receive the warning: "No solution found from 2 MIP starts" while solving the MP. Also, when the program is finished, I receive another warning: "Lazy constraints freed during column deletion". Is this anything to worry about? $\endgroup$
    – Arctic_Skill
    Commented Mar 20 at 8:47
  • 1
    $\begingroup$ I'm not positive, but it is possible that (a) you have advanced starts turned on and (b) CPLEX tries to start from the previous ending solution each time you invoke solve again. That might explain the MIP starts message, which would not worry me. As for the other message, I can see how deleting a column might make a constraint containing it irrelevant (perhaps implied by other constraints), allowing CPLEX to drop that constraint. Presumably the columns being deleted were dropped during presolve. $\endgroup$
    – prubin ♦
    Commented Mar 20 at 15:30

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.