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?
1 Answer
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).
-
$\begingroup$ I have no experience with clusters myself, but I wonder whether solving a problem with a decomposable structure on a cluster is faster using decomposition (farming out each subproblem to cluster node) than not (in which case, as I understand it, chunks of the full problem matrix get farmed out to nodes)? $\endgroup$– prubin ♦Jul 19, 2021 at 16:13
-
$\begingroup$ I have not seen a computational comparison of decomposition vs block-structured IPMs for large-scale problems on distributed-memory machines (aka clusters). I would expect the latter to be potentially better, but harder to implement. For more background reference: opus4.kobv.de/opus4-zib/files/7432/ip4energy3.pdf $\endgroup$– mtanneauJul 21, 2021 at 12:54