Optimization Online


Implementation of Warm-Start Strategies in Interior-Point Methods for Linear Programming in Fixed Dimension

Elizabeth John (lizjohn1***at***gmail.com)
E. Alper Yildirim (yildirim***at***bilkent.edu.tr)

Abstract: We implement several warm-start strategies in interior-point methods for linear programming (LP). We study the situation in which both the original LP instance and the perturbed one have exactly the same dimensions. We consider different types of perturbations of data components of the original instance and different sizes of each type of perturbation. We modify the state-of-the-art interior-point solver PCx in our implementation. We evaluate the effectiveness of each warm-start strategy based on the number of iterations and the computation time in comparison with ``cold start'' on the NETLIB test suite. Our experiments reveal that each of the warm-start strategies leads to a reduction in the number of interior-point iterations especially for smaller perturbations and for perturbations of fewer data components in comparison with cold start. On the other hand, only one of the warm-start strategies exhibits better performance than cold start in terms of computation time. Based on the insight gained from the computational results, we discuss several potential improvements to enhance the performance of warm-start strategies.

Keywords: Linear programming, interior-point methods, warm-start strategies, reoptimization

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Computational Optimization and Applications, 41 (2), pp. 151 - 183, 2008.


Entry Submitted: 05/11/2006
Entry Accepted: 05/11/2006
Entry Last Modified: 11/07/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society