Vortrag im Schwerpunkt Reelle Geometrie und Algebra
Freitag, 22. Januar 2010, um 10:15 Uhr in F420 (Oberseminar) (Achtung: Abweichende Uhrzeit und Raum!) Miguel Anjos (Waterloo/Köln) 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 is joint work with Alexander Engau
(University of Colorado-Denver) and Anthony Vannelli (University of
Guelph).
