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.
Type de document :
Communication dans un congrès
11th International Symposium on Experimental Algorithms, Jun 2012, Bordeaux, France. Springer, 2012, LNCS series
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00686255
Contributeur : François Vanderbeck <>
Soumis le : lundi 9 avril 2012 - 12:14:09
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : mercredi 14 décembre 2016 - 20:55:17

Fichier

feasPump18.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00686255, version 1

Collections

Citation

Pierre Pesneau, Ruslan Sadykov, François Vanderbeck. Feasibility Pump Heuristics for Column Generation Approaches. 11th International Symposium on Experimental Algorithms, Jun 2012, Bordeaux, France. Springer, 2012, LNCS series. 〈hal-00686255〉

Partager

Métriques

Consultations de la notice

386

Téléchargements de fichiers

383