An exterior simplex type algorithm for the Minimum Cost Network Flow Problem
| Autor: | Nikolaos Samaras, Konstantinos Paparrizos, Angelo Sifaleras |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Network simplex algorithm
Mathematical optimization General Computer Science Out-of-kilter algorithm Management Science and Operations Research Flow network Multi-commodity flow problem Simplex algorithm Modeling and Simulation Combinatorial optimization Minimum-cost flow problem Suurballe's algorithm Algorithm Mathematics |
| Zdroj: | Computers & Operations Research. 36:1176-1190 |
| ISSN: | 0305-0548 |
| DOI: | 10.1016/j.cor.2008.01.001 |
| Popis: | In this paper a new Network Exterior Point Simplex Algorithm (NEPSA) for the Minimum Cost Network Flow Problem (MCNFP) is analytically presented. NEPSA belongs to a special simplex type category and is a modification of the classical network simplex algorithm. The main idea of the algorithm is to compute two flows. One flow is basic but not always feasible and the other is feasible but not always basic. A complete proof of correctness for the proposed algorithm is also presented. Moreover, the computational behavior of NEPSA is shown by an empirical study carried out for randomly generated sparse instances created by the well-known GRIDGEN network problem generator. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect