Content area
The network simplex method, a minimum-cost network flow algorithm, was first created in 1956 by George Dantzig to solve transportation problems. This thesis improves upon Dantzig's method by pivoting two arcs instead of one at each iteration. The proposed algorithm is called the double-pivot network simplex method. Both leaving arcs are determined by solving a two-variable linear program. Due to the structure of these two-variable problems, this thesis also presents an approach to quickly solve them. The network and double-pivot network simplex methods make use of a modified eXtended Threading Index technique to efficiently create cycles and maintain the spanning tree basis. Computational experiments showed that the double-pivot network simplex method solved minimum-cost network flow problems from the NETGEN benchmark library using approximately 50% fewer total iterations, on average, than the network simplex method. In regards to CPU time, the double-pivoting method outperformed the network simplex algorithm by about 12% in large NETGEN instances. The network simplex method solved smaller NETGEN instances faster than the double-pivot network simplex method by approximately 8%. When averaging all instances, the double-pivoting method proposed in this thesis is over 5% faster than the network simplex method.