A WARM-START DUAL SIMPLEX SOLUTION ALGORITHM FOR THE MINIMUM FLOW NETWORKS WITH POSTOPTIMALITY ANALYSES

This paper presents an algorithm for finding the minimum flow in gener al (s,t) networks with m directed arcs. The minimum how problem (MFP) arises in many transportation and communication systems. Here, we cons truct a linear programming (LP) formulation of MFP and develop a simpl ex-type algorithm to find a minflow. Unlike other simplex-like algorit hms, the algorithm developed here starts with an incomplete Basic Vari able Set (BVS) initially and then fills-up the BVS completely while pu shing toward as, optimal vertex. if this results in pushing too far in to infeasibility, the next step pulls the solution back to feasibility . Both phases use the Gauss-Jordan pivoting transformation used in the standard simplex and dual simplex algorithms. The proposed approach h as some common features with Dantzig's self-dual simplex algorithm. We have avoided, however, the need for extra variables (slack and surplu s) for equality constraints, as well as an artificial constraint for t he self dual algorithm for initial phase and the dual simplex, respect ively. The proposed Push phase takes at most 2m - 1 iterations to comp lete a tree (this augmentation may not be feasible). An infeasible pat h to the optimal solution contains at most 2m - 1 iterations; therefor e in theory, the algorithm needs a sequence of at most 4m - 2 iteratio ns. Furthermore, the algorithm developed here makes available the full power of LP perturbation analysis and facilitates introducing network structural changes and side constraints also. It can also detect cler ical errors in data entry which may make the problem infeasible or unb ounded. It is assumed that the reader is familiar with LP terminology. (C) 1998 Elsevier Science Ltd. All rights reserved.