caa a22 4500 445879181 CHVBK 20180317145537.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s10601-009-9085-0 doi (NATIONALLICENCE)springer-10.1007/s10601-009-9085-0 Dantzig-Wolfe decomposition and branch-and-price solving in G12 [Elektronische Daten] [Jakob Puchinger, Peter Stuckey, Mark Wallace, Sebastian Brand] 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. Springer Science+Business Media, LLC, 2009 Modelling nationallicence Hybrid solving nationallicence Column generation nationallicence Branch and price nationallicence Puchinger Jakob Mobility Department, Austrian Institute of Technology, Vienna, Austria aut Stuckey Peter NICTA Victoria Research Laboratory, Department of Computer Science & Software Engineering, University of Melbourne, Melbourne, Australia aut Wallace Mark Faculty of Information Technology, Monash University, Melbourne, Australia aut Brand Sebastian NICTA Victoria Research Laboratory, Department of Computer Science & Software Engineering, University of Melbourne, Melbourne, Australia aut Constraints Springer US; http://www.springer-ny.com 16/1(2011-01-01), 77-99 1383-7133 16:1<77 2011 16 10601 https://doi.org/10.1007/s10601-009-9085-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10601-009-9085-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Puchinger Jakob Mobility Department, Austrian Institute of Technology, Vienna, Austria aut NATIONALLICENCE 700 1- Stuckey Peter NICTA Victoria Research Laboratory, Department of Computer Science & Software Engineering, University of Melbourne, Melbourne, Australia aut NATIONALLICENCE 700 1- Wallace Mark Faculty of Information Technology, Monash University, Melbourne, Australia aut NATIONALLICENCE 700 1- Brand Sebastian NICTA Victoria Research Laboratory, Department of Computer Science & Software Engineering, University of Melbourne, Melbourne, Australia aut NATIONALLICENCE 773 0- Constraints Springer US; http://www.springer-ny.com 16/1(2011-01-01), 77-99 1383-7133 16:1<77 2011 16 10601 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer