Title:Warm starts and hip cuts of interior-point methods in combinatorial optimization

We describe our two-year research effort to advance the use of interior-point methods for the solution of linear and semidefinite programming (LP/SDP) relaxations of combinatorial optimization problems. To accelerate or otherwise facilitate the re-optimization of successive relaxations, we first present a new warm-starting technique that uses additional slack variables to relax the non-negativity constraints on the original primal-dual variables and allows to re-use a previously optimal iterate as new interior starting point after data perturbations or the addition of cutting planes. For this approach, our preliminary results suggest iteration savings around 50% on average for perturbations of the Netlib linear programs and successive LP relaxations of the maximum-cut and the traveling-salesman problem. We then integrate this scheme into a hybrid interior-point cutting-plane method (HIPCUT) that does not solve successive relaxations to optimality but adds and removes cuts already at intermediate iterates based on feasibility indicators. Starting from the initial SDP relaxations for max-cut and the single-row facility-layout problem, our concluding computational results indicate that, using HIPCUT, we can find optimal solutions in less time than solving only the final relaxation with all relevant cuts already known in advance.
This is joint work with Miguel F. Anjos (University of Waterloo) and Anthony Vannelli (University of Guelph).