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

 

Abstract:
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" [...]

 

  loans online . But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra Without Prescription influence on blood clots.