Back to search

University of Macedonia Economic and Social Sciences

A dual network exterior point simplex-type algorithm for the minimum cost network flow problem

Abstract

dc:description

The Minimum Cost Network Flow Problem (MCNFP) refers to a wide category of network flow problems and it is an important research area of Network Optimization. A Dual Network Exterior Point Simplex Algorithm (DNEPSA) for the MCNFP is presented here. The algorithm belongs to the special category of Exterior Point Simplex-Type algorithms. Similarly to the classical Dual Network Simplex-type Algorithm (DNSA), DNEPSA starts with a dual feasible tree-solution and after a number of iterations, it produces a solution that is both primal and dual feasible, i.e. it is optimal. However, contrary to DNSA, the algorithm does not always maintain a dual feasible solution throughout all its iterations. Instead, it produces tree-solutions that can be infeasible for the dual problem and at the same time infeasible for the primal problem. The theoretical proof of correctness and the implementation details of DNEPSA are also presented. A detailed comparative computational study of DNEPSA against DNSA on sparse and dense random problem instances is presented and it is followed by the statistical analysis of the experimental results showing the effectiveness of DNEPSA compared to DNSA in terms of cpu time and iterations. The implementation of DNEPSA by using dynamic trees is also demonstrated and the algorithm’s amotized computational complexity per pivot is estimated.

Degree

thesis:*
Grantor dc:publisher
University of Macedonia Economic and Social Sciences
Year dc:date
2012

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Geranis, Georgios
  • Γεράνης, Γεώργιος

Subjects

dc:subject × 13

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/28548

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Geranis, Georgios; Γεράνης, Γεώργιος. A dual network exterior point simplex-type algorithm for the minimum cost network flow problem. University of Macedonia Economic and Social Sciences, 2012. http://hdl.handle.net/10442/hedi/28548