How Benders Decomposition Works, Part II: Feasibility Cuts

Benders decomposition encounters challenges when a master problem's solution results in an infeasible subproblem, preventing the generation of standard optimality cuts. To address this, feasibility cuts are introduced to restrict the master problem to decisions that admit a feasible operational solution. The mathematical tool for creating these cuts is Farkas' lemma, which provides a certificate of infeasibility for a system of linear constraints. This certificate is then converted into a new constraint for the master problem, effectively teaching it to avoid decisions that lead to impossible operational plans. The process is demonstrated first with a simple toy problem and then applied to a capacitated facility location problem.