An infeasible-interior-point potential-reduction algorithm for linear programming

An infeasible-interior-point potential-reduction algorithm for linear programming

0.00 Avg rating0 Votes
Article ID: iaor20003763
Country: Germany
Volume: 50
Issue: 2
Start Page Number: 313
End Page Number: 334
Publication Date: Jan 1999
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors:
Keywords: interior point methods
Abstract:

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 interior-point 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.

Reviews

Required fields are marked *. Your email address will not be published.