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 | 20th International Symposium of Mathematical Programming - Chicago, IL, United States Duration: 23 Aug 2009 → 28 Aug 2009 Conference number: 20 http://ismp2009.eecs.northwestern.edu/ |
Conference
Conference | 20th International Symposium of Mathematical Programming |
---|---|
Number | 20 |
Country/Territory | United States |
City | Chicago, IL |
Period | 23/08/2009 → 28/08/2009 |
Internet address |