| Autor: |
Jeffery L. Kennington, Richard V. Helgason |
| Rok vydání: |
1995 |
| Předmět: |
|
| DOI: |
10.1016/s0927-0507(05)80119-7 |
| Popis: |
Publisher Summary This chapter discusses primal simplex algorithms for minimum cost network flows. Due to the special structure of bases for the linear network flow model, specialized simplex-based software can solve these problems in from one to two orders of magnitude faster than general linear programming software. The chapter summarize the ideas fundamental to efficient software implementation of the primal simplex algorithm for minimum cost network flow problems and indicate how these ideas have been extended for generalized networks, multicommodity networks, and networks with arbitrary side constraints. The specialized algorithms presented in this chapter all rely on the graphical interpretation of the simplex steps when applied to a linear program possessing an underlying network structure, in whole or in part. Graphical characterizations for bases for both the linear network problem and the generalized network problem can be found. Additional elaboration on the interpretation of the algebraic operations on a graphical structure is provided. The first software implementations which empirically demonstrated the merit of those specialized algorithms were developed. The algorithms presented in the chapter were generally based on a specialization of the simplex method. There are three other basic approaches which are now competing quite successfully in empirical analyses. The oldest is the relaxation method. The second is the algorithm of Goldberg which has been implemented in software. The third algorithm which could have an impact on the field is the network interior point method. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
