What is a feasibility cut in Benders decomposition?

Question

I am currently learning about solving problems with iterations, and my text states that:

At every iteration a violated optimality or feasibility cut is found and added to MP

I am however quite lost to what is meant by that.

Answer 1

A Benders feasibility cut is a valid inequality, in terms of the master variables, that is required for feasibility of the subproblem but is violated by the current master solution. MP is an abbreviation for Master Problem.

Questions about Benders decomposition will probably get more attention here.

Answer 2

I'm getting into Benders decomposition at the moment, so it's a perfect timing! You want to solve something like this: master problem: $\min_{x} c^T x + f(x), s.t. Ax \le b, x \ge 0$
where subproblem: $f(x) = \min\{d^T y ~|~ Dy \le d - Cx, y \ge 0\}$.

When you write the dual of the subproblem, the feasible set becomes independent of the master's variables $x$. Now:

• if the dual is bounded (that is the primal is feasible), the solution $y$ is a corner of the feasible set. Since the dual is a max problem, its solution for a given $x$ gives you a lower bound on $f$: that's an optimality cut ;
• if the dual is unbounded (that is the primal is infeasible), the solver terminates with an extreme ray $r$. If you move towards a direction that makes an acute angle with $r$, you diverge. So you add a feasibility cut to force the solution to make an obtuse angle with $r$.