If the original problem contains the diagonal block structure property or other specific properties then we can apply column generation or other decomposition algorithms to solve it.

However, if the problem with overlapping blocks (for example, a variable appears into two more blocks) instead of diagonal block. How could we use decomposition algorithms to solve it? Is any related literature recommended?

  • 2
    $\begingroup$ Search for Lagrangian decomposition, which introduces copies of variables for this purpose. $\endgroup$
    – RobPratt
    Jan 9 at 13:44
  • $\begingroup$ @RobPratt Thanks for sharing. I'll check it. $\endgroup$
    – ytsao
    Jan 9 at 14:48


Your Answer

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