About combinatorial Benders Cuts

I am solving an OR scheduling problem where I assign the patient to (day,OR) tuple in Master Problem. Once the assignment is made, a subproblem can be solved for each (day,OR) tuple independently where patients are assigned to a time slot t. A cost of idle time/overtime is incurred.

Master problem is given by

$$Z_{MP} = \min \sum_{d=1}^{\delta} \sum_{k=1}^{K} [c^k Q_{dk} + \theta_{dk}]$$ $$\sum_{i=1}^{N} X_{idk} \leq Q_{dk}, \quad \forall d \in \mathbb{D}, k \in \mathbb{K},$$ $$Q_{dk} \geq Q_{dk'}, \quad \forall k, k' \in \mathbb{K}, k' > k, d \in \mathbb{D},$$ $$\sum_{d=1}^{\delta} \sum_{k=1}^{K} X_{idk} = 1 \hspace{1in} \forall i \in \mathbb{N}$$ $$\text{Combinatorial benders cuts}$$ $$X_{idk} \in \{0,1\}, Q_{dk} \in \{0,1\}, \theta_{dk} \geq 0$$ Where Q determines whether OR is opened or not, while X is the assignment variable. Solving this problem gives me as set of surgeries for each $$\mathbb{N}_{dk}$$ for which subproblem is solved. The assignment in the master problem changes the structure of my subproblem. That is, it is possible to have 2 surgeries assigned to (day1, OR1) in one iteration while it could be 4 in the next iteration. The cut added is of the form where $$Z^{SP}_{dk}$$ is cost of subproblem for (d,k). $$\theta_{dk} \geq Z^{SP}_{dk} - (Z^{SP}_{dk} - L) (\sum_{i: X^*_{idk} = 0} X_{idk} + \sum_{i: X^*_{idk}=1} (1-X_{idk}) )$$

1. Using this form, I add a cut for each (day = d,OR=k) tuple, if $$\theta_{dk} < Z^{SP}_{dk}$$ This cut essentially ensures that the solution is not repeated or the solution that is found is at least >= L (Lower Bound). The subproblem has the cost of idle time, overtime, and a cost of starting surgery $$i$$ in a particular timeslot $$t$$ i.e. $$C_{idtk}$$. Also must be noted that adding surgery for (day p, OR q) another (day r,OR s) may reduce the cost of the (r,s) depending on the comparison of idle time cost vs $$C_{it}$$ parameter. The convergence is too slow and some additional strengthening cuts do not work which are discussed Benders Decomposition cuts for MILP problem with further separable subproblems How can this be improved.

2. It is ensured in the master problem that surgeries assigned to (day, OR) do not exceed the capacity of OR. Is it beneficial to let the master problem find infeasible solutions for its subproblems and then add a feasibility cut of the above form? Does that help with the convergence?

• The Benders cut you generate is known to be quite weak; it basically says "if you do exactly this, the cost is so much, and if you do anything else, I have no idea what the cost is going to be". You can try to find something in the structure of the subproblem that yields a tighter cut, but my personal success rate finding tighter cuts is not encouraging. Sep 30 '21 at 17:45