Title | ||
---|---|---|
Computational experience with a modified potential reduction algorithm for linear programming |
Abstract | ||
---|---|---|
We study the performance of a homogeneous and self-dual interior point solver for linear programming LP that is equipped with a continuously differentiable potential function. Our work is motivated by the apparent gap between the theoretical complexity results and long-step practical implementations in interior point algorithms. The potential function described here ensures a global linear polynomial-time convergence while providing the flexibility to integrate heuristics for generating the search directions and step length computations. Computational results on standard test problems show that LP problems are solved as efficiently in terms of the number of iterations as Mosek6. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1080/10556788.2011.634911 | Optimization Methods and Software |
Keywords | Field | DocType |
computational result,apparent gap,self-dual interior point solver,interior point algorithm,computational experience,potential function,modified potential reduction algorithm,global linear polynomial-time convergence,long-step practical implementation,differentiable potential function,lp problem,linear programming lp,interior point method,interior point methods,computer experiment,interior point,polynomial time,linear program,linear programming | Linear-fractional programming,Convergence (routing),Mathematical optimization,Algorithm,Heuristics,Linear programming,Solver,Smoothness,Interior point method,Mathematics,Algebraic interior | Journal |
Volume | Issue | ISSN |
27 | 4-5 | 1055-6788 |
Citations | PageRank | References |
4 | 0.41 | 13 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sanjay Mehrotra | 1 | 521 | 77.18 |
Kuo-Ling Huang | 2 | 80 | 4.95 |