# How to modify Benders decomposition to handle overlapping or shared variables among the subproblems

I have a problem that can be separated into a master problem and two subproblems, SP-A and SP-B. SP-B share some variables with SP-A, and the shared/overlapping variables from SP-A cannot be fixed for SP-B, otherwise it will lose coherence in its formulation. Can this still be addressed under the Benders decomposition framework without integrating the two subproblems?

No not directly. Let's say that there's only one shared variable $$y$$ between SP-A and SP-B, and that you create 2 subproblems SP-A and SP-B with a local copy of the shared variable $$y$$, namely $$y_A$$ and $$y_B$$. Next you solve SP-A and SP-B. The optimal solutions to those 2 subproblems may have different values for $$y_A$$ and $$y_B$$. If $$y_A$$ and $$y_B$$ were forced to take the same values then the subproblems could return very different solutions as one value of $$y$$ might be feasible for one problem but not for the other and vice versa.
2. Introduce local copies of the variables, e.g. $$y_A$$ and $$y_B$$ in the above example, add the constraint $$y_A=y_B$$ and dualize this constraint using a Lagrangian. This decouples your problem. For more details, refer to Lagrangian decomposition.
• Hi Joris, would adding the constraint $y_A=y_B$ mean that the two subproblems have to coordinate? That is, would they have to be solved sequentially? Commented Dec 19, 2023 at 16:15
• @user4444 as mentioned, you'd have to apply a lagrangian decomposition to get rid of the $y_a=y_b$ constraint. As a result you'll have to solve the 2 subproblems multiple times because you'll have to update the lagrangian multipliers but you can solve the subproblems separately and in parallel. Commented Dec 19, 2023 at 22:36
• Thank you. Visualizing this, it seems like a hierarchical decomposition now. At the top-level iteration, after solving the MP I will fix its variables for SP-A and SP-B. I will then iteratively solve SP-A and SP-B until they converge for $y_A$ and $y_B$. Thereafter, I will then proceed to the next iteration of my Benders solution. Is my thinking correct? Commented Dec 20, 2023 at 1:18