Abstract
When applying Interior Point (IP) algorithm to the solution of linear or convex separable optimization problems with strong graph structure, like the Min Cost Flow (MCF) problem, one has to repeatedly solve linear systems with strong graph structure. One of the two possible approach leads to systems with a M-matrix that is basically the weighted Laplacian of the underlying graph, where the weights (but not the graph) change at each iteration of the IP methods and typically become “very imbalanced” at the last ones. For this problem we have used two different techniques: Preconditioned Conjugate Gradient (PCG) methods, based on the idea of extracting a proper triangulated subgraph of the original graph which strictly contains a spanning tree. We have defined a new class of triangulated graphs, called Brother-Connected Trees (BCT), and discuss some fast heuristics for finding BCTs of “large” weight, starting from either the Kruskal algorithm or the Prim one. In addition we have studied multi-iterative techniques where the above PCG approach has been combined with specialized coarser-grid operators which preserve the graph structure of the projected matrix at the inner levels and smoothers, that have been completely characterized. Quite a lot of work still remains to do for understanding which is the best combination of preconditioning and coarsening at different stages of the overarching IP algorithm, implementing these techniques in an efficient solver, and extending them to “truly” interesting graph-structured problems like Multicommodity MCF ones. Everyone is welcome!