3
$\begingroup$

Is there a difference between logical and combinatorial Benders Decomposition and the cutting plane method?

My understanding is that for all of these techniques, there is a MIP and based on solutions to the problem new constraints are generated and added to the problem until the solution is optimal. Are these just different names for the same technique or is there real difference?

$\endgroup$
6
$\begingroup$

I'm going to assume that "the cutting plane method" refers to branch and cut (branch and bound with cuts added at the root and possibly other nodes), as opposed to older cutting plane algorithms that relied exclusively on adding cuts to the LP relaxation (no branching).

I would consider branch and cut different from logical or combinatorial Benders (or original Benders, for that matter), because in branch and cut the cuts are derived from the structure/properties of the master problem, while Benders cuts are derived from a different problem. (Note that solvers used on the Benders master problem will also generate non-Benders cuts.)

Now it's fair to ask whether Benders cuts are different from the cuts you would get if you did not use Benders decomposition and solved a single (larger) MIP model. For "traditional" Benders, I don't think a solver attacking the combined problem would generate those particular cuts, but I'm not positive. For logical/combinatorial Benders, I would say no, for either of two reasons. In some cases, the Benders decomposition is letting you avoid big-M constraints, so the original MIP is not just the merger of the master and subproblems in combinatorial Benders, but is structurally somewhat different.

Also, depending on how you interpret "combinatorial Benders" and "logical Benders", there are versions of them in which the subproblem is not an LP and possibly not even a MIP. It's some external problem that somehow coughs up a linear constraint when the master problem solution is not to its liking. Those constraints would not occur as one of the standard types of cuts supported by the MIP solver, and in any case the non-LP/non-MIP nature of the subproblem might prevent having a single MIP model at all.

$\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.