Research ArticleOpen AccessGoogle Scholar indexed
Optimal Adjustment Algorithm for <i>p</i> Coordinates and The Starting Point in Interior Point Methods
- 1
- 2
- 3
American Journal of Operations Research·Volume 01 (2011)·Pages 191–202·Published 21 December 2011·DOI10.4236/ajor.2011.14022
Copy link · social · email
Abstract
Optimal adjustment algorithm for <i>p</i> coordinates is a generalization of the optimal pair adjustment algorithm for linear programming, which in turn is based on von Neumann’s algorithm. Its main advantages are simplicity and quick progress in the early iterations. In this work, to accelerate the convergence of the interior point method, few iterations of this generalized algorithm are applied to the Mehrotra’s heuristic, which determines the starting point for the interior point method in the PCx software. Computational experiments in a set of linear programming problems have shown that this approach reduces the total number of iterations and the running time for many of them, including large-scale ones.
KeywordsVon Neumann’s AlgorithmMehrotra’s HeuristicInterior Point MethodsLinear Programming
- G. B. Dantzig, “Converting A Converging Algorithm into a Polynomially Bounded Algorithm,” Technical Report, Stanford University, SOL 91-5, 1991.
- G. B. Dantzig, “An ?-Precise Feasible Solution to a Linear Program with a Convexity Constraint in 1/?2 Iterations Independent of Problem Size,” Technical Report, Stanford University, SOL 92-5, 1992.
- M. Epelman and R. M. Freund, “Condition Number Complexity of an Elementary Algorithm for Computing a Reliable Solution of a Conic Linear System,” Mathematical Programming, Vol. 88, No. 3, 2000, pp. 451-485.
- J. P. M. Gon?alves, “A Family of Linear Programming Algorithms Based on the Von Neumann Algorithm,” Ph.D. Thesis, Lehigh University, Bethlehem, 2004.
- J. P. M. Gon?alves, R. H. Storer and J. Gondzio, “A Family of Linear Programming Algorithms Based on an Algorithm by Von Neumann,” Optimization Methods and Software, Vol. 24, No. 3, 2009, pp. 461-478. doi:10.1080/10556780902797236
- J. Silva, “Uma Família de Algoritmos para Programa??o Linear Baseada no Algoritmo de Von Neumann,” Ph.D. Thesis, IMECC-UNICAMP, Campinas, 2009 (in Portu- guese).
- S. Mehrotra, “On the Implementation of a Primal-Dual Interior Point Method,” SIAM Journal on Optimization, Vol. 2, No. 4, 1992, pp. 575-601.
- H. Y. Benson and D. F. Shanno, “An Exact Primal Dual Penalty Method Approach to Warm Starting Interior- Point Methods for Linear Programming,” Computational Optimization and Applications, Vol. 38, No. 3, 2007, pp. 371-399. doi:10.1007/s10589-007-9048-6
- E. John and E. A. Yildirim, “Implementation of Warm- Start Strategies in Interior-Point Methods for Linear Pro- gramming in Fixed Dimension,” Computational Optimization and Applications, Vol. 41, No. 2, 2008, pp. 151- 183. doi:10.1007/s10589-007-9096-y
- A. Engau, M. F. Anjos and A. Vannelli, “A Primal-Dual Slack Approach to Warm Starting Interior-Point Methods for Linear Programming,” Operations Research and Cy- ber-Infrastructure, Vol. 47, 2009, pp. 195-217. doi:10.1007/978-0-387-88843-9_10
- G. B. Dantzig and M. N. Thapa, “Linear Programming 2: Theory and Extensions,” Springer-Velag, New York, 1997.
- D. Bertsimas and J. N. Tsitsiklis, “Introduction to Linear Optimization,” Athena Scientific, Belmont, 1997.
- J. Czyzyk, S. Mehrotra, M. Wagner and S. J. Wright, “PCx an Interior Point Code for Linear Programming,” Optimization Methods & Software, Vol. 11, No.1-4, 1999, pp. 397-430. doi:10.1080/10556789908805757