Is an insanely high number of feasibility cuts normal while solving a VRP with Benders?

Question

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?

Answer 1

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!