I needed to decompose a large LP of equality constraints. $\\Dx=B^1,$ $\\Ax=B^2,$ $\\D \in R^{m^{(1)} \times n} $ $\\A\in R^{m^{(2)} \times n}, m<<n$
$A$ has a block diagonal structure and $D$ is formed for some link constraints which may span all variables.
I was suggested to use Dantzig-Wolfe Decomposition followed by the Column Generation algorithm. While reading these, I found that this algorithm uses extreme points of each segment as a starting point and builds all the feasible points in the segment as a convex combination of these extreme points. What I don't understand is how can we assume to have all these extreme points. Is there a computationally efficient way of doing this? Or is my understanding wrong?
A description of the method often starts with the full set of extreme points (and extreme rays), but these are typically generated dynamically via a column generation subproblem. In practice, only a small subset of all possible extreme points (and extreme rays) are needed. You can use a two-phase approach (like in the simplex method), where the first phase finds a feasible solution and the second phase finds an optimal solution. If you can otherwise construct a set of columns that together yield a feasible master solution, you can skip the first phase.