3
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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:

  1. Fix shared variables in the master problem. As such, these variables become constants in the subproblem.
  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.
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – user4444
    Dec 19, 2023 at 16:15
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 19, 2023 at 22:36
  • $\begingroup$ 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? $\endgroup$
    – user4444
    Dec 20, 2023 at 1:18
  • 1
    $\begingroup$ @user4444 yes that's correct $\endgroup$ Dec 20, 2023 at 22:29

Your Answer

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