Universität zu Köln
Mathematisch-Naturwissenschaftliche Fakultät
Arbeitsgruppe Faigle/Schrader
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).