Are decomposition methods applicable on large linear programs?

Question

Working on a very large Linear Program, we tried out some primitive implementations of decomposition techniques such as Lagrangian relaxation and column generation. However, none of these were able to only come close to computation times achieved with the Barrier algorithm. Thus, we assume that these decomposition approaches only work well on Integer Programs, which is why they are almost solely discussed for IPs in the literature. This would indicate that LPs are "well-solved" with the Simplex algorithms and methods such as Barrier or Interior-point. Is there any literature that investigates that point or comes to an equivalent solution?

Answer 1

As a general rule of thumb, I would say that if you have an LP that fits in your memory, then directly applying barrier/simplex is likely to be the best "out-of-the-box" approach.

In my experience, decomposition techniques, such as Lagrangean/Benders/Dantzig-Wolfe decomposition, work best (and outperform barrier/simplex) in the following situations (the list is non-exhaustive):

• The original LP is too large to fit in the memory. For instance, you have a large two-stage stochastic LP with a lot of scenarios, or your LP is the master problem in a Dantzig-Wolfe decomposition (which often has exponentially many variables). In that case, you can't handle the problem without decomposing it.

• The problem has a special structure that you know how to exploit. A famous example is the multi-commodity network flow problem, where the textbook decomposition yields one min-cost-flow problem per commodity. In that case, you can use specialized solvers for the subproblems, which may accelerate the overall method.

I should note here that, if you have a block-structured LP, then you can also apply a barrier or simplex algorithm with specialized, typically distributed, linear algebra. If you want more background, I can refer you to the introduction of this paper (of which I'm a co-author).