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 metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-00686255
Contributor : François Vanderbeck <>
Submitted on : Monday, April 9, 2012 - 12:14:09 PM
Last modification on : Thursday, January 11, 2018 - 6:22:12 AM
Long-term archiving on : Wednesday, December 14, 2016 - 8:55:17 PM

File

feasPump18.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00686255, version 1

Citation

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⟩

Share

Metrics

Record views

424

Files downloads

458