### Abstract

This talk concerns the NP-hard Maximum Multicommodity k-splittable Flow Problem (MMCkFP) in which each commodity may use at most k paths between its origin and its destination. A new branch-and-cut-and-price algorithm is presented. The master problem is a two-index formulation of the MMCkFP and the pricing problem is the shortest path problem with forbidden paths. A new branching strategy forcing and forbidding the use of certain paths is developed. The new branch-and-cut-and-price algorithm is computationally evaluated and compared to results from the literature. The new algorithm shows very promising performance by outperforming existing algorithms for several instances.

Original language | English |
---|---|

Title of host publication | Proceedings of the 20th International Symposium of Mathematical Programming 2009 (ISMP'09) |

Publication date | 2009 |

Publication status | Published - 2009 |

Event | The 20th International Symposium of Mathematical Programming 2009 (ISMP'09) - Chicago, US Duration: 1 Jan 2009 → … |

### Conference

Conference | The 20th International Symposium of Mathematical Programming 2009 (ISMP'09) |
---|---|

City | Chicago, US |

Period | 01/01/2009 → … |

## Cite this

Gamst, M., & Petersen, B. (2009). An Exact Solution Approach for the Maximum Multicommodity K-splittable Flow Problem. In

*Proceedings of the 20th International Symposium of Mathematical Programming 2009 (ISMP'09)*http://ismp2009.eecs.northwestern.edu/printfiles/ScheduleFriday.pdf