Jakob Puchinger, Peter J. Stuckey, Mark G. Wallace and Sebastian Brand

Title of Article

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

Title Of Journal

Constraints

PublishInfo

Springer

Publication Year

2011

Volum

16

Issue Number

1

Page

77-99

Keywords

Modelling , Hybrid solving , Column generation , Branch and price

Notes

براي دانلودو مشاهده مقاله به قسمت لينكهاي مرتبط مراجعه نماييد

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.

URL

http://www.springerlink.com/content/l2186h750668l3g3/,/DL/Data Entry/DataEntryForm/EnterDocInfo.aspx,/DL/Data Entry/NewEdit/Documents/Math_English_Electronic_Articles_EditDoc_925.aspx