# Benders Decomposition cuts for MILP problem with further separable subproblems

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 overtime is incurred if OR is occupied beyond a certain time slot.

It is ensured in the master problem that the assignment to each OR,day tuple is feasible. Thus, the subproblems are always feasible.

The benders cut added is of the form

Using this form, I add a cut for each (day,OR) tuple, if $$\phi(x^*)_{dk} > \sigma^*_{dk}$$ This cut essentially ensures that the solution is not repeated or the solution that is found is at least >= M (Lower Bound).

The cuts added from the relaxation of SP are valid for the original problem. However, is that the case when you further separate the problem as I have done before? Can I add the cuts from LP relaxation for each (OR,day) tuple?

I ask this question because I obtain the solution only when I have integer cuts of the form above, however, the lower bound is violated when I include the cuts from SP relaxation. Under what condition the cuts from LP relaxation are valid?

• Are you asking about adding both the "no good" cuts in the image and the cuts from the LP dual, or are you asking about using the LP cuts instead of the "no good" cuts? Aug 7 at 18:03
• I want to use both the cuts however using cuts from LP dual in addition to no-good cuts resulted in the solution higher than optimal solution for the problem. It means that cuts from LP dual are removing integer feasible solutions. Referring to the book "50 years of integer programming", the cuts added from LP relaxation of subproblems should also be valid. But could the case be different if I further decompose the problem by (day,OR) tuple? Could this be case that the cuts generated from individual problems are not valid anymore? Aug 7 at 18:48
• You'll have to write out a subproblem and the cut you are generating from it for this to be answered. Aug 7 at 22:28
• $$\min c^u U + c^o O + \sum_{t \in T,i \in N_{dk}} \lambda_{it} X_{it}$$ $$t * Z_{it} - O \leq S \quad \forall t \in T ,i \in N_{dk}$$ $$s - \sum_{i \in N_{dk}} \sum_{t = 1}^{S} Z_{it} \leq U$$ $$\sum_{t' = t}^{t+l_i-1} Z_{it'} \geq l_i * X_{it} \quad \forall i \in N_{dk}, 1 \leq t \leq T-l_i+1$$ $$\sum_{t \in T} Z_{it} = l_i \quad \forall i \in N_{dk}$$ $$\sum_{i \in N_{dk}} Z_{it} \leq 1 \quad \forall t \in T$$ $$\sum_{t \in T} X_{it} = 1 \quad \forall i \in N_{dk}$$ $$\sum_{t = T-l_i+1}^{T} X_{it} = 0 \quad \forall i \in N_{dk}$$ $$O,U \geq 0, X,Z_{it} \in \{0,1\}$$ Aug 9 at 18:02
• @prubin I missed a constraint above constraint 8 = $$Z_{it} \geq X_{it} \quad \forall i \in N_{dk}, t \in T$$ I am generating cuts for above problem by using .Pi attribute from each constraint, where my cut is written as $$\sigma_{dk} \geq \sum_{t \in T, i \in N_{dk}} S*{\Pi^1}_{it} + S {\Pi^2} + 0 \Pi^3 + \sum_{i \in N_{dk}} l_i {\Pi^4}_i + \sum_{t \in T} 1 {\Pi^5}_{it} + \sum_{i \in N_{dk}} 1 {\Pi^6}_{i} + 0 \Pi^7 + 0 \Pi^8$$ $X_{it}$: Binary- surgery i starts in time slot t $Z_{it}$: Binary- surgery i occupies time slot t $O$: Overtime $U$: Idletime $S$: SessionLength Aug 9 at 18:43

It sounds like your Benders master problem is to minimize $$\sigma = \sum_{d,k} \sigma_{d,k}$$, where your independent subproblems are indexed by $$(d,k)$$. For each fixed master solution $$x^*$$, let $$\phi(x^*)_{d,k}$$ be the optimal objective value (or any lower bound, perhaps obtained from the LP relaxation) of subproblem $$(d,k)$$, and let $$M$$ be a valid lower bound on $$\sigma_{d,k}$$. Then the following constraint ("combinatorial Benders optimality cut") is valid: $$\sigma_{d,k} \ge \phi(x^*)_{d,k} - (\phi(x^*)_{d,k} - M) \left(\sum_{j: x_j^* = 0} x_j + \sum_{j: x_j^* = 1} (1-x_j)\right) \tag1$$ This (big-M) constraint enforces the logical implication $$x=x^* \implies \sigma_{d,k} \ge \phi(x^*)_{d,k}$$.
But this cut can be very weak. If every subset of the support of $$x^*$$ yields $$\sigma_{d,k} \ge \phi(x^*)_{d,k}$$, you can strengthen as follows: $$\sigma_{d,k} \ge \phi(x^*)_{d,k} - (\phi(x^*)_{d,k} - M) \sum_{j: x_j^* = 0} x_j \tag2$$
Similarly, if every superset of the support of $$x^*$$ yields $$\sigma_{d,k} \ge \phi(x^*)_{d,k}$$, you can strengthen as follows: $$\sigma_{d,k} \ge \phi(x^*)_{d,k} - (\phi(x^*)_{d,k} - M) \sum_{j: x_j^* = 1} (1-x_j) \tag3$$
• Thank you for elaborating the my question here in perfect way for everyone to understand. The objective function is $min Z = \sum_{dk} \sigma_{dk} + C^fQ_{dk}$. Where I minimize the fixed cost of opening the OR and $\sigma_{dk}$. The cut I have is exactly the way you described by equation 1. I still do not understand what you mean by subset/superset of support of x. Can you please help with little details so that I can include cuts given by equation 2 and 3 in correct manner? Aug 7 at 20:54
• Constraint (1) applies when the conditional is $x=x^*$, that is $\land_j (x_j = x_j^*)$. Constraint (2) applies when the conditional is $\land_j (x_j \le x_j^*)$. Constraint (3) applies when the conditional is $\land_j (x_j \ge x_j^*)$. Aug 7 at 21:22
• Please provide me reference if you can find it. I did not find the above cuts in the book but as you say, I am sure that they must have been mentioned in the book. A question about the cuts, here in (2) and (3), the $x_j^*$ mentioned are all the variables in master problem is that correct? For example, I have $X_{idk}$ as MP variable. When I solve subproblem for (d,k), value for $X_{idk} = 0$ for all $i \notin N_{dk}$, so the cut (2) will not be valid cut if the cut is written for $i \in N_{dk}$ instead of $i \in N$. Can you confirm this? Is this also true for cut (3) Aug 21 at 18:51