An Infeasible-Interior-Point Potential-Reduction Algorithm
for Linear Programming
Reha Tutuncu
This paper studies a new potential-function and an infeasible-interior-point
method based on this function for the solution of linear programming
problems. This work is motivated by the apparent gap between the
algorithms with the best worst-case complexity and their most successful
implementations. For example, analyses of the algorithms are usually
carried out by imposing several regularity assumptions on the problem,
but implementations can solve problems which do not satisfy these
assumptions. Furthermore, most state-of-the-art implementations
incorporate heuristic tricks, but these modifications are rarely
addressed in the theoretical analysis of the algorithms. The method
described here and its analysis have the flexibility to integrate any
heuristic technique for implementation while maintaining the important
polynomial complexity feature.
Technical Report 1136, School of Operations Research and Industrial
Engineering, Cornell University, Ithaca, NY.
Contact: tutuncu@orie.cornell.edu
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)