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

A new dual simplex type algorithm for the Minimum Cost Network Flow Problem (MCNFP) is presented. The proposed algorithm belongs to a special “exteriorpoint simplex type” category. Similarly to the classical network dual simplex algorithm (NDSA), this algorithm starts with a dual feasible tree-solution and reduces the primal infeasibility, iteration by iteration. | Yugoslav Journal of Operations Research Vol 19 (2009), Number 1, 157-170 DOI: A DUAL EXTERIOR POINT SIMPLEX TYPE ALGORITHM FOR THE MINIMUM COST NETWORK FLOW PROBLEM George GERANIS Konstantinos PAPARIZZOS Angelo SIFALERAS Department of Applied Informatics, University of Macedonia, geranis,paparriz,sifalera@ Received: December 2007 / Accepted: May 2009 Abstract: A new dual simplex type algorithm for the Minimum Cost Network Flow Problem (MCNFP) is presented. The proposed algorithm belongs to a special “exteriorpoint simplex type” category. Similarly to the classical network dual simplex algorithm (NDSA), this algorithm starts with a dual feasible tree-solution and reduces the primal infeasibility, iteration by iteration. However, contrary to the NDSA, the new algorithm does not always maintain a dual feasible solution. Instead, the new algorithm might reach a basic point (tree-solution) outside the dual feasible area (exterior point - dual infeasible tree). Keywords: Operations research, combinatorial optimization, minimum cost network flow problem. 1. INTRODUCTION The Minimum Cost Network Flow Problem (MCNFP) is the problem of finding a minimum cost flow of product units, through a number of source nodes, sinks and transshipment nodes. Other common problems, such as the shortest path problem, the transportation problem, the transshipment problem, the assignment problem etc., are the special cases of the MCNFP. Such problems appear very frequently in different technology sectors, like the Information Technology, the Telecommunications, the Transportation, the Resource Management, etc. Algorithms developed for the MCNFP can offer good solutions for such problems. A number of different problems that can be solved by the following MCNFP methods are described in [1] and [9]. 158 G. Geranis, K. Paparrizos, / Minimum Cost Network The MCNFP can be easily transformed into a Linear Programming Problem and well known general linear