Dantzig-Wolfe decomposition and branch-and-price solving in G12 - Archive ouverte HAL Access content directly
Journal Articles Constraints Year : 2011

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

(1) , (2, 3) , (4) , (2, 3)


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.
Fichier principal
Vignette du fichier
bp_g12.pdf (232 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01224910 , version 1 (05-11-2015)



Jakob Puchinger, Peter J. Stuckey, Mark Wallace, Sebastian Brand. Dantzig-Wolfe decomposition and branch-and-price solving in G12. Constraints, 2011, 16 (1), pp.77-99. ⟨10.1007/s10601-009-9085-0⟩. ⟨hal-01224910⟩
70 View
1710 Download



Gmail Facebook Twitter LinkedIn More