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.
Two alternatives to overcome this issue:
- Fix shared variables in the master problem. As such, these variables become constants in the subproblem.
- 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.