Treffer: Acceleration of cutting-plane and column generation algorithms : Applications to network design
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Weitere Informationen
Most of integer, convex, and large-scale linear problems are solved using cutting plane and column generation algorithms. Therefore, to handle large-size problems and to reduce the computing times, it may be very useful to accelerate cutting plane algorithms. We show in this article that we can achieve this goal by choosing good separation points. Focus is given on problems for which we have an exact separation oracle. An in-out algorithm is proposed, and the convergence is proved under some general assumptions. Computational experiments related to three classes of problems, survivable network design, multicommodity flow problems, and random linear programs, clearly point out the savings of time allowed by the simple in-out approach proposed in this article.