3
$\begingroup$

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

enter image description here

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?

Improve this question
$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$
    – prubin ♦
    Commented Aug 7, 2021 at 18:03
  • $\begingroup$ 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? $\endgroup$
    – Amogh Bhosekar
    Commented Aug 7, 2021 at 18:48
  • $\begingroup$ You'll have to write out a subproblem and the cut you are generating from it for this to be answered. $\endgroup$
    – prubin ♦
    Commented Aug 7, 2021 at 22:28
  • $\begingroup$ $$ \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\}$$ $\endgroup$
    – Amogh Bhosekar
    Commented Aug 9, 2021 at 18:02
  • $\begingroup$ @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 $\endgroup$
    – Amogh Bhosekar
    Commented Aug 9, 2021 at 18:43

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
16
  • $\begingroup$ 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? $\endgroup$
    – Amogh Bhosekar
    Commented Aug 7, 2021 at 20:54
  • 1
    $\begingroup$ 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^*)$. $\endgroup$
    – RobPratt
    Commented Aug 7, 2021 at 21:22
  • $\begingroup$ Can you please provide me reference to above cuts that you have mentioned? I would like to learn more about it? $\endgroup$
    – Amogh Bhosekar
    Commented Aug 16, 2021 at 20:45
  • $\begingroup$ I don't have my copy in front of me, but I believe both (2) and (3) are mentioned in the "50 Years of Integer Programming" book you referenced. $\endgroup$
    – RobPratt
    Commented Aug 16, 2021 at 20:50
  • 1
    $\begingroup$ For (2), consider two cases: $\sum_{j:x_j^*=0} x_j = 0$ and $\sum_{j:x_j^*=0} x_j \ge 1$. The first case corresponds to the support of $x$ being a subset of the support of $x^*$, and (2) reduces to the assumed inequality. The second case corresponds to the support of $x$ not being a subset of the support of $x^*$, and (2) is redundant by the choice of big-M. So (2) is valid in both possible cases. $\endgroup$
    – RobPratt
    Commented Nov 9, 2022 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.