1
$\begingroup$

In Benders decomposition algorithm, we first solve a master problem which provides us with a solution vector. We then use this vector to construct a subproblem. For a minimization problem, subproblems give an upper bound (since it is a restricted version of the original problem). If the upper bound is strictly greater than the lower bound (provided by master problem, a relaxation of the original problem) then we add a Benders cut to remove this point (i.e., the solution vector obtained from master problem).

I understand why this Benders (optimality) cut is used to remove such point from master problem, but I don't understand why it is valid. In other words, this point is not the only point which is removed from the feasible region of master problem when this cut is added. Can someone explain the rationale behind this in simple terms? On the other hand, there might be many more cuts that can remove this point. Why among those cuts we can (usually) only prove that Benders cuts are valid?

$\endgroup$
1
$\begingroup$

Actually, for a minimization problem the subproblem generates a cut that is a lower bound on the portion of the original objective function coming from the subproblem variables.

The key to understanding this is duality theory. The values of the integer variables coming from the master problem modify the right hand side limits of the subproblem constraints. That's equivalent to modifying the objective coefficients of the dual to the subproblem. So the dual solution you get is feasible (in the dual) for all possible integer variable values (since they are not messing with the dual constraints) and optimal for that particular set of variable values. You construct both kinds of cuts, optimality (lower bound) and feasibility (when the primal subproblem is infeasible/dual is unbounded), from the dual solution, so the fact that the dual solution does not depend on the master problem values to be feasible makes the cuts globally valid.

As far as other (non-Benders) cuts go, it is entirely possible for some of them to be provably valid and cut off a given solution. I'm just not aware of any that are uniformly provably valid (valid for all decomposable MIP models). The proof that some other flavor of cut is globally valid will likely depend on some particular aspect of the problem, something like having a known type of IP model (knapsack, set covering, TSP, ...) embedded within the given problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.