Master Problem Infeasible after Iterations of Unbounded Sub Problem (Generic Benders Decomposition in non Stochastic MILP)

Question

I am dealing with a large problem of MILP problem and interested to apply Benders Decomposition. I have already check the original problem and it was feasible to run in large number of computation time. I understand in some sources: stackexchangelink and ProfRubinblog that somewhat a careful implementation should be done. I found that after several iterations of unbounded dual sub problem, my master problem had become infeasible. Due to the fact that the original problem is feasible, I suppose that I have to identify cut to add in my master problem.

My question is: When I can't calculate the original problem using traditional method (and that's the reason of using Benders Decomposition), is there a way to know the boundary of the cause of in-feasibility between adding a new cut in my master problem and the in-feasibility of the problem it self?

Answer 1

If the original problem was feasible, the Benders master problem should never become infeasible. You may have a formulation error in the Benders decomposition, or you may be generating the cuts incorrectly.

If you can identify a feasible (not necessarily good) solution to the problem by solving the original formulation, you can use that to locate any errors in your Benders approach. Fix the master variables at their values in the feasible solution and run the subproblem. If the subproblem is infeasible (dual unbounded), fix the values of the subproblem variables at their values in the feasible solution and look for violated constraints.