0
$\begingroup$

I am in the process of trying to solve a VRP with synchronization constraints with Benders Decomposition. I am programming in C++ and my approach seems to be really slow for the following reason:

My VRP is a MIP with a minimization objective function. Thus, my SP is a maximization problem and my MP is a minimization problem.

I start the algorithm by initializing the integer variables with 0 as is usual practice, I solve the subproblem, which is optimal in that case but with quite a high obj. value giving me a first upper bound.

My program generates an optimality cut and passes on to the MP. The MP finds a solution, which is set as the lower bound. It passes on the integer variable values to the SP to go into the second interation.

Now this process is obviously repeated until LB = UB.

But: Starting from iteration 2, each time the subproblem is unbounded and it stays like this really long. Meaning we never see a feasible MP solution until the optimum is found.

The problem is:

Right now, I'm just testing with two simple instances. For the first one, it needs 366 iterations to find the optimum. Meaning we generated 1 optimality cut in iteration 1 and then 365 feasibility cuts until we got a feasible MP solution again.

In the second example instance, it doesn't even find the optimal solutions. After over 2000 iterations, where apart from iteration 1, it only ever generated feasibility cuts, the programs stops without a solution.

Now, these two are instances that are solved within milliseconds in CPLEX standard solver. Even when I set Benders strategy to FULL in CPLEX, they are solved quickly with much less cuts that have to be generated.

Do you know why my program could behave like this? Is it something that could be wrong in my programming or is this something that happens in Benders normally?

$\endgroup$
2
  • 1
    $\begingroup$ For a minimization problem, the Benders master problem and subproblem are both minimization because the master problem arises from omitting original constraints and the subproblem arises from fixing original variables. For VRP, fixing all master variables to $0$ should not be feasible to the subproblem, so you should get a feasibility cut instead of an optimality cut. Did you maybe dualize the subproblem to get a maximization? $\endgroup$
    – RobPratt
    Sep 15, 2023 at 13:33
  • $\begingroup$ Yes, I am working with the dual subproblem. $\endgroup$ Sep 18, 2023 at 7:05

1 Answer 1

3
$\begingroup$

You usually use Benders decomposition when a large number of variables and linking constraints can somehow be removed without significantly affecting the structure of your problem.

In your case, you have a VRP with sync constraints. You remove the sync from the MP (variables and associated constraints), and find yourself solving a regular VRP with no synchronization.

Your solver, say at iteration 2, is finding a VRP solution that does not take into account synchronization. Then you find a feasibility cut to cut that solution. The result: you will find another solution that also does not care about synchronization. If the MP includes many solutions that do not respect the synchronization constraints, you may be adding Benders cuts forever. Each time you will be adding a feasibility cut only to find that the solver in the next iteration finds another bad solution.

If the cost of synchronization is high, things are even worse. Your solver will be enumerating the cheapest solutions possible. This means that you will potentially enumerate a large number of solutions without synchronization being respected. This is most likely what you are observing.

What can you do to mitigate this behavior? There are several techniques available:

  1. Use dual stabilization techniques to separate deep cuts, this is cuts that not only cut the current solution but potentially my neighboring solutions as well. Matteo Fischetti has for many years studied ways to achieve this. You could start by looking at this short article https://link.springer.com/article/10.1007/s10107-010-0365-7
  2. Integrate in your MP some notions of syncronization. This is, does not remove sychnronization entirely, but add some variables and constraints to make sure that synchronization is roughly enforced at the MP level. Think of leaving in the MP all the same synchronization constraints but aggregated in groups. There are several implementations of this idea in the literature but I do not remember any of them by heart at this time (sorry).

Good luck with your research!

$\endgroup$
3
  • $\begingroup$ Thank you for that explanation! That helps a lot. So I guess I can assume I implemented Benders correctly and the bad performance is due to my problem structure? $\endgroup$ Sep 18, 2023 at 7:07
  • 1
    $\begingroup$ Well I haven't seen your model so you should not assume anything :-), but what you are telling us is consistent with the situation I described above. So it could be the case of a perfectly implemented BD that just behaves poorly for those reasons $\endgroup$ Sep 18, 2023 at 14:12
  • $\begingroup$ Yeah, that's true ;). I will try understanding and implementing acceleration techniques. Hope it helps. $\endgroup$ Sep 19, 2023 at 7:08

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.