Dantzig-Wolfe decomposition and branch-and-price solving in G12

Abstract : The G12 project is developing a software environment for stating and solving combinatorial problems by mapping a high-level model of the problem to an efficient combination of solving methods. Model annotations are used to control this process. In this paper we explain the mapping to branch-and-price solving. Dantzig-Wolfe decomposition is automatically performed using the additional information given by the model annotations. The models obtained can then be solved using column generation and branch-and-price. G12 supports the selection of specialised subproblem solvers, the aggregation of identical subproblems to reduce symmetries, automatic disaggregation when required by branch-and-bound, the use of spe-cialised subproblem constraint-branching rules, and different master problem solvers including a hybrid solver based on the volume algorithm. We demonstrate the benefits of the G12 framework on three examples: a trucking problem, cutting stock, and two-dimensional bin packing.
Type de document :
Article dans une revue
Constraints, Springer Verlag, 2011, 16 (1), pp.77-99. 〈10.1007/s10601-009-9085-0〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01224910
Contributeur : Jakob Puchinger <>
Soumis le : jeudi 5 novembre 2015 - 11:53:55
Dernière modification le : dimanche 22 janvier 2017 - 12:13:48
Document(s) archivé(s) le : samedi 6 février 2016 - 11:18:25

Fichier

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

Identifiants

Collections

Citation

Jakob Puchinger, Peter Stuckey, Mark Wallace, Sebastian Brand. Dantzig-Wolfe decomposition and branch-and-price solving in G12. Constraints, Springer Verlag, 2011, 16 (1), pp.77-99. 〈10.1007/s10601-009-9085-0〉. 〈hal-01224910〉

Partager

Métriques

Consultations de la notice

73

Téléchargements de fichiers

638