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.