Invited Session Fri.2.H 2038

Friday, 13:15 - 14:45 h, Room: H 2038

Cluster 4: Conic programming [...]

Warmstarting interior point methods


Chair: Jacek Gondzio



Friday, 13:15 - 13:40 h, Room: H 2038, Talk 1

Anders Skajaa
Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems

Coauthors: Erling D. Andersen, Yinyu Ye


We present two strategies for warmstarting primal-dual interior point methods for the homogeneous self-dual model when applied to mixed linear and quadratic conic optimization problems. Common to both strategies is their use of only the final (optimal) iterate of the initial problem and their negligible computational cost. This is a major advantage when comparing to previously suggested strategies that require a pool of iterates from the solution process of the initial problem. Consequently our strategies are better suited for users who use optimization algorithms as black-box routines which usually only output the final solution. Our two strategies differ in that one assumes knowledge only of the final primal solution while the other assumes the availability of both primal and dual solutions. We present extensive computational results showing work reductions when warmstarting compared to coldstarting in the range 30 to 75 percent depending on the problem class and magnitude of the problem perturbation. The computational experiments thus substantiate that the warmstarting strategies are useful in practice.



Friday, 13:45 - 14:10 h, Room: H 2038, Talk 2

E. Alper Yildirim
Warm-start strategies: What matters more?


The problem of solving a sequence of closely related optimization
problems arises frequently in sequential optimization algorithms and branch-and-bound-like schemes. The information gained during the solution of an optimization problem can in principle be used to solve a closely related optimization problem with less computational effort. The proper use of this information constitutes warm-start techniques. In this talk, our goal is to focus on the criteria in the design of warm-start strategies and to identify which ones are more closely related to the success in practice.



Friday, 14:15 - 14:40 h, Room: H 2038, Talk 3

Pablo González-Brevis
A new warm-starting strategy for the primal-dual column generation method

Coauthor: Jacek Gondzio


In this presentation a new warm-starting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems will be addressed. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after new columns arrive. Conditions on the maximum size of the cuts from the dual perspective and on a suitable initial point will be discussed. This strategy ensures that the duality gap of the warm-start is bounded by the old duality gap and a constant, which depends on the relation between the old and modified problems. Additionally, computational experience using this strategy will be reported.


  Getting Payday Loans In California should be thought of many times. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.