This thesis explores applications of Interior Point methods as popularized by Karmarkar (36) for solving Multicommodity Network Flow problems (MCNF). In these problems, several commodities must be shipped between various nodes of a network. The goal is to satisfy the shipping requirements at a minimum cost, while respecting processing capacities on the joint flow of commodities. The thesis presents a unified view of current methods for multicommodity networks, from the early formulations to current work that has involved nonlinear and interior point methods. It compares and contrasts some Interior Point methods, and discusses how they can be applied to the MCNF problem. It builds upon the first Interior Point partitioning method proposed to solve MCNF, and implements a related partitioning method. This scheme allows network subproblems to be solved using efficient network simplex algorithms: then the results are coordinated using a linear program that is solved with an Interior Point affine scaling algorithm. It presents computational results, comparing the results from the partitioning method with those found by solving an LP formulation of the problem using the affine scaling method.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/6760 |
| Date | January 1993 |
| Creators | Browne, Christopher B. |
| Contributors | Thizy, Jean-Michel, |
| Publisher | University of Ottawa (Canada) |
| Source Sets | Université d’Ottawa |
| Detected Language | English |
| Type | Thesis |
| Format | 144 p. |
Page generated in 0.1645 seconds