The Multi-Point Separation Strategy as a Column Generation Stabilization Technique

François Vanderbeck 1, 2 Artur Alves Pessoa 1 Ruslan Sadykov 2, 1 Eduardo Uchoa 1
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : Column generation suffers from slow convergence. Algorithmic strategies have been designed to accelerate convergence of cutting plane algorithms in mixed integer programming. They have their counterpart in column generation. We show that the "Multi-Point Separation" strategy translates into a column generation stabilization technique that consists in restricting the dual solution to be in the convex hull of the selected multi-point set.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01108143
Contributor : François Vanderbeck <>
Submitted on : Thursday, January 22, 2015 - 11:32:35 AM
Last modification on : Thursday, January 11, 2018 - 6:22:12 AM

Identifiers

  • HAL Id : hal-01108143, version 1

Citation

François Vanderbeck, Artur Alves Pessoa, Ruslan Sadykov, Eduardo Uchoa. The Multi-Point Separation Strategy as a Column Generation Stabilization Technique. INFORMS Annual Meeting 2014, Nov 2014, San Francisco, United States. ⟨hal-01108143⟩

Share

Metrics

Record views

684