An Interior Dual Proximal Point Algorithm for Linear Programs

Abstract

An interior point algorithm for obtaining a proximal point solution of a linear program is presented. Results from our implementation of this algorithm have been very encouraging. For 36 test problems including 32 NETLIB problems, we obtain a total time speedup of 5.6 over the MINOS 5.0 simplex package. We also describe an implantation of our algorithm for linear programs with upper-bounded variables, such as the multicommodity Patient Distribution System models of the Military Airlift Command. We have been able to solve some of these multicommodity problems with 8-figure accuracy and speedup of as much as 24 over the MINOS 5.0. Furthermore, our run times on the Astronautics ZS-1 are comparable with those of AT&T's KORBX times for some of the problems.