Computer Sciences Dept.

An Interior Dual Proximal Point Algorithm for Linear Programs

Rudy Setiono

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.

Download this report (PDF)

Return to tech report index

Computer Science | UW Home