Tuesday, 15:15 - 15:40 h, Room: H 2032


Tiziano Parriani
An analysis of natural approaches for solving multicommodity-flow problems

Coauthors: Alberto Caprara, Antonio Frangioni


We study the relative performances of three existing approaches to solve the minimum-cost linear MultiCommodity Flow Problem (MCFP). The first approach is solving the LP corresponding to the natural node-arc formulation with state-of-the-art, general-purpose commercial software. The second is to take advantage of the block-diagonal structure with complicating constraints of the LP to develop Dantzig-Wolfe decomposition/column generation approaches. The third is a decomposition-based pricing procedure, proposed by Mamer and McBride, in which the same subproblems of the D-W decomposition are used to identify new columns in a reduced master problem that has the same structure of the node-arc formulation. With a particular focus on degeneracy and instability issues of the column generation, different classes of MCFP instances are solved in order to study the connections between the structure of a specific instance and the performances of the most common solving approaches for this class of problems. This may be useful in choosing the correct approach when a particular MCFP shall be solved, as well as improving the effectiveness of the approaches themselves.


Talk 1 of the invited session Tue.3.H 2032
"Trends in mixed integer programming V" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  signature loans . In this section we give only a brief summary recommendation for admission of Canadian Levitra. Full information can be found in the instructions for receiving medications with vardenafil.