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

by

Emre Alper Yıldırım
Bilkent University


Abstract: Having solved a linear programming (LP) problem with an interior-point method (IPM), we consider the situation in which we are presented with a new LP instance with the same problem dimension, whose data is a slight perturbation of the original LP problem. We implement strategies for recovering a "warm-start" point for the perturbed problem instance from the iterates of the original problem instance using the interior-point solver PCx. We consider several warm-start strategies, including those developed by Yildirim and Wright. Our extensive numerical experiments on NETLIB problems demonstrate that some of the strategies lead to efficient reoptimization under random perturbations of the coefficient matrix A, the right-hand side vector b, and/or the cost vector c.