Combinatorial Feasibility Cuts for Benders Decomposition

Question

Are there any advantages of adding constraints in the Benders master problem that ensure the feasibility of the subproblems? This would not add any feasibility cuts. Or is it beneficial to have a master problem find an assignment and then determine feasibility in the subproblem? Or this does not matter?

I am solving a scheduling problem where I assign patients to operating rooms with deterministic surgery durations in the master problem. In the subproblem, patients are sequenced and costs are calculated. I can include constraints such that no OR gets assigned the number of patients where the total surgery duration does not exceed 8 hours capacity. I am only adding the no-good type of cuts for optimality.

Answer 1

I'm not aware that either approach is automatically better than the other. Once consideration regarding putting feasibility constraints in the master problem is whether they would likely be violated in the subproblem were they not already present. If you are adding a large number of feasibility constraints in the master (relative to a small number that would otherwise be generated in the subproblem), you might be slowing the solver down unnecessarily.

This also may be solver-dependent. With CPLEX, for instance, you could add the feasibility constraints to the master as "lazy constraints", meaning that they for the most part sit to one side and are only checked when CPLEX thinks it has an integer-feasible candidate solution. If any lazy constraints are violated by that solution, they become active (at least for a while) and the candidate is discarded. Some other solvers may have similar features that prevent the feasibility constraints from being a drag on performance.

Answer 2

The trade-off you want to make is: (1) how hard is it to solve the master problem (and hence, how much time does it take), and (2) how many Benders iterations does it take to find a feasible/optimal solution (depends on what you are looking for). This you can best determine through some benchmarking.

As a rule-of-thumb, you want to add a relaxation of the subproblem to the master problem, to guide the master problem in the right direction. The trick here is to keep the master problem light enough that it can be solved efficiently.

A standard example is the capacitated facility location problem where the master problem determines which facilities to open while minimizing opening costs, and the subproblem solves an assignment problem to assign customers to opened facilities while minimizing assignment costs. Since the master problem attempts to minimize the total cost to open facilities, in the first iteration, in the absence of any constraints, the master problem will not open any facilities at all. Consequently, the subproblem will return a feasibility cut, because non of the customers can be assigned to a facility. Many more of these iterations may follow until finally a feasible solution is discovered. Many of these iterations could have been avoided if you had added a constraint to the master problem stating that at least a minimum number of facilities should be opened in order to permit a feasible solution (this minimum could be determined by solving a bin-packing problem).

Answer 3

If you are adding constraints to the master to ensure the subproblem is feasible you are básically adding the entire feasible region of the subproblem as constraints in the master, therefore you are defeating the point of doing the Benders partition in the first place.