Implementation of multiple-corrections and presolve enhancement in the interior-point linear programming code LIPSOL

[摘要] Multiple correction was introduced by Gondzio (5) to accelerate the convergence of iterates generated by primal-dual interior-point algorithms for linear programming. In this work, we implement the multiple correction technique in the interior-point linear programming software LIPSOL with our modifications. In our implementation, we have used modified criteria to start and stop the multiple correction process in order to achieve high efficiency under the LIPSOL environment. In addition, we have implemented a more thorough presolve analysis to enhance the solver's efficiency. The main presolve technique addressed in this work is to eliminate implied free variables. We have performed extensive computational experiments on the Netlib set of linear programs as well as on some larger linear programs from real-world applications. On the average, our implementation of the enhanced presolve and the multiple correction technique has resulted in a 10% to 20% saving in CPU time.

[发布机构] Rice University

[效力级别] Computer