3
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you so much Prof. Rubin. $\endgroup$ Jan 21, 2022 at 2:28

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.