Combinatorial Benders decomposition is a mathematical programming technique consisting into dividing a problem into a master problem and a sub problem. The master problem is solved to optimality (or alternatively for a MIP, every time a potential new best solution is identified while branching) and then the associated subproblem is solved. If the subproblem is feasible then the solution of the master problem is a (optimal) solution to the original problem. Otherwise a new constraint is added to the master problem to cut the current solution.
An example of this could be the following (even though I would guess that the results would be quite deceiving): If our original problem is the Capacitated Vehicle Routing Problem, a way to solve it using Benders decomposition would be to use the VRP as a master problem and in the subproblem to check that each vehicle respects its capacity constraints. If the capacity constraints are not respected we add a constraint stating that at least one arc used in the current (master problem) solution cannot be used.
In order to be able to successfully use this solution method, what are some characteristics that the original problem should display?
I have the felling that the subproblem should not be too constraining (in the sense, that for an arbitrary solution of the master problem there should be a good chance that the subproblem is feasible), but would be interested by any data backing (or refuting) this up.
Edit: One of the comments of @Michael Trick made me realise that there exist more variation of Benders decomposition than I was aware of. For clarification purposes I was referring to Combinatorial Benders decomposition .