Dr. Miguel Anjos
Universtiy of Waterloo, Ontario, Canada
Department of Management Sciences

Warm-starts for interior-point methods in combinatorial optimization

We present a new warm-starting technique for re-optimizing successive linear programming problems when using interior-point methods. The idea is that a previously optimal solution can be used as the initial point for re-starting an interior-point method by suitably relaxing the non-negativity constraints using additional slack variables. Computational results show that the iteration savings can be up to 50% on average. This warm-starting technique is then integrated into a semidefinite programming interior-point cutting-plane algorithm that achieves greater efficiency by adding and removing valid inequalities as the interior-point method progresses. Preliminary computational results show that we can find optimal solutions in less time than solving the final relaxation with all relevant cuts known in advance. This methodology is now being incorporated into a general-purpose branch-and-cut solver for combinatorial optimization problems. This is joint work with Alexander Engau (University of Colorado Denver) and Anthony Vannelli (University of Guelph).