Warm Start of the Primal-Dual Method Applied in the Cutting Plane Scheme

Jacek Gondzio

A practical warm start procedure is described for the primal-dual interior point method employed to solve the restricted master problem within the cutting plane method.

In contrast to the theoretical developments in this field, the approach presented in this paper does not make the unrealistic assumption that the new cuts are shallow. Moreover, it treats systematically the case when a large number of cuts is added at the time.

The technique proposed in this paper has been implemented in the context of HOPDM, the state of the art, yet public domain, interior point code. Numerical results confirm a high efficiency of the approach: regardless the number of cuts added at the time (that grows to thousands in the largest examples) and regardless the depth of the new cuts, reoptimizations are usually done in several iterations.

Logilab Technical Report 96.3, Section of Management Studies, University of Geneva, 102 Bd Carl Vogt, CH-1211 Geneva 4, Switzerland, May, 1996. (Revised April, 1997).

Contact: gondzio@divsun.unige.ch