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?