Basic Observations
Keep the coupling constraints at a superior level, in a Master Problem;
this with the goal of obtaining a Column Generator which is rather easy to solve.
solve the Column Generator, which is often separable in several independent sub-problems;
use a specialized algorithm that exploits its particular structure.