Skip to Main content Skip to Navigation
New interface
Conference papers

Feasibility Pump Heuristics for Column Generation Approaches

Pierre Pesneau 1, 2 Ruslan Sadykov 1, 2 François Vanderbeck 1, 2 
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 : Primal heuristics have become an essential component in mixed integer programming (MIP). Generic heuristic paradigms of the literature remain to be extended to the context of a column generation so- lution approach. As the Dantzig-Wolfe reformulation is typically tighter than the original compact formulation, techniques based on rounding its linear programming solution have better chance to yield good primal so- lutions. However, the dynamic generation of variables requires specific adaptation of heuristic paradigms. We focus here on "feasibility pump" approaches. We show how such methods can be implemented in a context of dynamically defined variables, and we report on numerically testing "feasibility pump" for cutting stock and generalized assignment prob- lems.
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : François Vanderbeck Connect in order to contact the contributor
Submitted on : Monday, April 9, 2012 - 12:14:09 PM
Last modification on : Saturday, June 25, 2022 - 7:46:17 PM
Long-term archiving on: : Wednesday, December 14, 2016 - 8:55:17 PM


Files produced by the author(s)


  • HAL Id : hal-00686255, version 1



Pierre Pesneau, Ruslan Sadykov, François Vanderbeck. Feasibility Pump Heuristics for Column Generation Approaches. 11th International Symposium on Experimental Algorithms, Ralf Klasing, Jun 2012, Bordeaux, France. ⟨hal-00686255⟩



Record views


Files downloads