×

Warm start of the primal-dual method applied in the cutting-plane scheme. (English) Zbl 0920.90102

Summary: A practical warm-start procedure is described for the infeasible 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 are added at one 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 degree of efficiency of this approach: regardless of the number of cuts added at one time (can be thousands in the largest examples) and regardless of the depth of the new cuts, reoptimizations are usually done with a few additional iterations.

MSC:

90C10 Integer programming

Software:

HOPDM; ACCPM
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andersen, E.; Gondzio, J.; Meszaros, C.; Xu, X.; Terlaky, T., Implementation of interior point methods for large scale linear programming, Interior Point Methods in Mathematical Programming, 189-252 (1996), Dordrecht: Kluwer Academic Publisher, Dordrecht · Zbl 0874.90127
[2] Arioli, M.; Duff, I. S.; de Rijk, P. P.M., On the augmented system approach to sparse least-squares problems, Numerische Mathematik, 55, 667-684 (1989) · Zbl 0678.65024 · doi:10.1007/BF01389335
[3] Goffin, J.-L.; Contesse, L.; Correa, R.; Weintraub, A., The ellipsoid method and its predecessors, Recent Advances in System Modelling and Optimization, 127-141 (1987), Berlin: Springer, Berlin · Zbl 0606.90104 · doi:10.1007/BFb0006784
[4] Goffin, J.-L.; Gondzio, J.; Sarkissian, R.; Vial, J.-P., Solving nonlinear multicommodity flow problems by the analytic center cutting plane method, Mathematical Programming, 79, 131-154 (1997) · Zbl 0881.90050
[5] Goffin, J.-L.; Haurie, A.; Vial, J.-P., Decomposition and nondifferentiable optimization with the projective algorithm, Management Science, 38, 2, 284-302 (1992) · Zbl 0762.90050 · doi:10.1287/mnsc.38.2.284
[6] Goffin, J.-L.; Vial, J.-P., Cutting planes and column generation techniques with the projective algorithm, Journal of Optimization Theory and Applications, 65, 409-429 (1990) · Zbl 0676.90041 · doi:10.1007/BF00939559
[7] Gondzio, J., Multiple centrality corrections in a primal-dual method for linear programming, Computational Optimization and Applications, 6, 137-156 (1996) · Zbl 0860.90084
[8] Gondzio, J., HOPDM (ver. 2.12)—A fast LP solver based on a primal-dual interior point method, European Journal of Operational Research, 85, 221-225 (1995) · Zbl 0925.90284 · doi:10.1016/0377-2217(95)00163-K
[9] Gondzio, J.; du Merle, O.; Sarkissian, R.; Vial, J.-P., ACCPM—A library for convex optimization based on an analytic center cutting plane method, European Journal of Operational Research, 94, 206-211 (1996) · doi:10.1016/0377-2217(96)00169-5
[10] Gondzio, J.; Sarkissian, R., Column generation with the primal-dual method (1996), Switzerland: Department of Management Studies, University of Geneva, Switzerland
[11] Gonzaga, C. C., Path-following methods for linear programming, SIAM Review, 34, 167-224 (1992) · Zbl 0763.90063 · doi:10.1137/1034048
[12] Hipolito, A. L., A weighted least squares study of robustness in interior point linear programming, Computational Optimization and Applications, 2, 29-46 (1993) · Zbl 0799.90081 · doi:10.1007/BF01299141
[13] Jansen, B.; Roos, C.; Terkaky, T.; Vial, J.-P., Primal-dual target following algorithms for linear programming, Annals of Operation Research, 62, 197-231 (1996) · Zbl 0848.90083 · doi:10.1007/BF02206817
[14] Kelley, J. E., The cutting plane method for solving convex programs, Journal of the SIAM, 8, 703-712 (1960) · Zbl 0098.12104
[15] Lustig, I. J.; Marsten, R. E.; Shanno, D. F., Computational experience with a globally convergent primaldual predictor-corrector algorithm for linear programming, Mathematical Programming, 66, 123-135 (1994) · Zbl 0811.90068 · doi:10.1007/BF01581140
[16] Lustig, I. J.; Marsten, R. E.; Shanno, D. F., Interior point methods for linear programming: Computational state of the art, ORSA Journal on Computing, 6, 1-14 (1994) · Zbl 0798.90100
[17] Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM Journal on Optimization, 2, 4, 575-601 (1992) · Zbl 0773.90047 · doi:10.1137/0802028
[18] du Merle, O.; Goffin, J.-L.; Vial, J.-P., On the comparative behavior of Kelley’s cutting plane method and the analytic center cutting plane method (1996), Switzerland: Logilab, Department of Management Studies, University of Geneva, Switzerland
[19] J.E. Mitchell, Karmarkar’s Algorithm and Combinational Optimization Problems, Ph.D. Thesis, Cornell University, 1988.
[20] Vial, J.-P., A generic path-following algorithm with a sliding constraint and its application to linear programming and the computation of analytic centers (1996), Switzerland: Logilab, Department of Management Studies, University of Geneva, Switzerland
[21] Wright, S. J., Primal-Dual Interior-Point Methods (1997), Philadelphia: SIAM, Philadelphia · Zbl 0863.65031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.