Experimental investigations in combining primal dual interior point method and simplex based LP solvers.

*(English)*Zbl 0836.90117Summary: The use of a primal dual interior point method (PD) based optimizer as a robust linear programming solver is now well established. Instead of replacing the sparse simplex algorithm (SSX), the PD is increasingly seen as complementing it. The progress of PD iterations is not hindered by the degeneracy or stalling problem of SSX, indeed it reaches the “near optimum” solution very quickly. The SSX algorithm, in contrast, is not affected by the numeral instabilities which slow down the convergence of the PD near the optimal face. If the solution to the LP problem is non- unique, the PD algorithm converges to an interior point of the solution set while the SSX algorithm finds an extreme point solution.

To take advantage of the attractive properties of both the PD and the SSX, we have designed a hybrid framework whereby crossover from PD to SSX can take place at any stage of the PD optimization run. The crossover to SSX involves the partition of the PD solution set to active and dormant variables. In this paper, we examine the practical difficulties in partitioning the solution set, we discuss the reliability of predicting the solution set partition before optimality is reached and report the results of combining exact and inexact prediction with SSX basis recovery.

To take advantage of the attractive properties of both the PD and the SSX, we have designed a hybrid framework whereby crossover from PD to SSX can take place at any stage of the PD optimization run. The crossover to SSX involves the partition of the PD solution set to active and dormant variables. In this paper, we examine the practical difficulties in partitioning the solution set, we discuss the reliability of predicting the solution set partition before optimality is reached and report the results of combining exact and inexact prediction with SSX basis recovery.

##### Keywords:

primal dual interior point method; robust linear programming solver; sparse simplex algorithm; hybrid
PDF
BibTeX
XML
Cite

\textit{R. Levkovitz} and \textit{G. Mitra}, Ann. Oper. Res. 58, 19--38 (1995; Zbl 0836.90117)

Full Text:
DOI

##### References:

[1] | I. Adler and R.D.C. Monteiro, A geometric view of parametric linear programming, Algorithmica 8(1992)161–176. · Zbl 0767.90042 · doi:10.1007/BF01758841 |

[2] | A. Altman and J. Gondzio, An efficient implementation of higher order primal dual interior point method for large scale programming, Systems Research Institute, Polish Academy of Sciences, Newelska 6, 01447, Poland (1992). |

[3] | R.E. Bixby, Implementing the simplex method: the initial basis, TR-90-32, Department of Mathematical Sciences, Rice University, Houston, TX 77251, USA (December 1990). · Zbl 0759.90063 |

[4] | R.E. Bixby, J.W. Gregory, I.J. Lustig, R.E. Marsten and D.F. Shanno, A very large scale linear programming: a case study in combining interior point and simplex methods, Oper. Res. 40(1992)885–897. · Zbl 0758.90056 · doi:10.1287/opre.40.5.885 |

[5] | R.E. Bixby and M.J. Saltzman, Recovering an optimal basis from an interior point solution, Technical Report #607, Department of Mathematical Sciences, Clemson University, Clemson, South Carolina, USA (March 1992). · Zbl 0814.90073 |

[6] | A.S. El-Bakry, R.A. Tapia and Y. Zhang, A study of indicators for identifying zero variables in interior point methods,ICIAM 91, Washington, DC (1991). · Zbl 0801.65056 |

[7] | J. Forrest and J.A. Tomlin, OSL optimization subroutine library version 2.0,User Guide and Reference Manual (IBM, 1990). |

[8] | B. Jansen, C. Roos, T. Terlaky and J.Ph. Vial, Interior-point methodology for linear programming: duality, sensitivity analysis and computational aspects, Technical Report 93-28, Faculty of Technical Mathematics and Informatics, Delft University, Deflt, The Netherlands (1993). |

[9] | D.M. Gay, Stopping tests that compute optimal solutions for interior point linear programming algorithms, Proceedings in Applied Mathematics Vol. 47:Advances in Numerical Partial Differential Equations and Optimization, Proc. 5th Mexico-US Workshop, ed. S. Gomez, J.P. Hennart and R.A. Tapia (Siam, 1991) pp. 17–42; Numerical Analysis Manuscript 89-11, AT&T Bell Labora-tories, Murray Hill, NJ 07974, USA (December 1989). |

[10] | O. Guler and Y. Ye, Convergence behaviour of some interior point algorithms, Working Paper 91-4, The College of Business administration, The University of Iowa, Iowa City, IA (1991). |

[11] | O. Guler, C. Roos, T. Terlaky and J.-Ph. Vial, Interior point approach to the theory of linear programming, Research Report 1992.3, Faculté des Sciences Economiques et Sociales, Université de Genève (February 1992). |

[12] | R. Levkovitz, G. Mitra and M. Tamiz, Integration of the interior point method within simplex: experiments in feasible basis recovery,APMOD91 Symp., Brunel University, UK (January 1991). |

[13] | R. Levkovitz, Interior point methods for large scale linear programs, theory and computational algorithms, Ph.D. Thesis, Brunel University, Uxbridge, UK (October 1992). |

[14] | J. Lustig, W. Marsten and F. Shanno, On implementing Mehrotra’s predictor corrector interior point method for linear programming, SIAM J. Optim. 2(1992)435–439. · Zbl 0771.90066 · doi:10.1137/0802022 |

[15] | N. Megiddo, Switching from a primal dual Newton algorithm to a primal dual (interior) simplex algorithm, RJ 6327 (61996), Computer Science/Mathematics, IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120-6099, USA (November 1988). |

[16] | N. Megiddo and M. Shub, Boundary behaviour of interior point algorithms in linear programming, Math. Oper. Res. 14(1989). · Zbl 0675.90050 |

[17] | N. Megiddo, On finding primal and dual optimal bases, ORSA J. Comp. 3(1991). · Zbl 0755.90056 |

[18] | S. Mehrotra, High order methods and their performance, Technical Report 90-16R1, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60208-3119, USA (July 1990). |

[19] | S. Mehrotra and Y. Ye, On finding the optimal facet of linear programming, Technical Report 91-10, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60208-3119, USA (June 1991). |

[20] | G. Mitra, M. Tamiz and J. Yadegar, Experimental investigation of an interior search method within a simplex framework, Commun. ACM 21(1988). |

[21] | R.J. Vanderbei, ALPO: Another Linear Program Optimizer, ORSA J. Comput. 5(1993). · Zbl 0777.90031 |

[22] | Y. Zhang and A. Tapia, On the convergence of interior point methods to the centre of the solution set in linear programming, Department of Mathematics and Statistics, University of Maryland, Baltimore County Campus, Baltimore, MD 21228, USA (September 1991). |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.