Invited Session Tue.3.H 2032

Tuesday, 15:15 - 16:45 h, Room: H 2032

Cluster 11: Integer & mixed-integer programming [...]

Trends in mixed integer programming V


Chair: Andrea Lodi and Robert Weismantel



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

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.



Tuesday, 15:45 - 16:10 h, Room: H 2032, Talk 2

Alexandra Mary Newman
Practical guidelines for solving difficult linear and mixed integer programs

Coauthor: Ed Klotz


The advances in state-of-the-art hardware and software have enabled
the inexpensive, efficient solution of many large-scale linear and
linear integer programs previously considered intractable. However,
a significant number of real-world linear and linear integer
programs can still require hours, or even days, of run time and are
not guaranteed to yield an optimal (or near-optimal) solution. In this talk, we present
suggestions for diagnosing and removing performance problems in
commercially available linear and mixed integer programming solvers,
and guidelines for careful model formulation. We draw on examples from the mining and
energy industries, among other areas.


  There are three major facts that should be watched out for in all payday loans in the United States. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.