Dantzig-Wolfe decomposition and branch-and-price solving in G12 |
| |
Authors: | Jakob Puchinger Peter J Stuckey Mark G Wallace Sebastian Brand |
| |
Affiliation: | (1) Department of Management Science, School of Business Administration, University of Miami, Coral Gables, FL 33124-8237, USA |
| |
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 specialised 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|