Dantzig-Wolfe Decomposition and Branch-and-Price Solving in G12

Jakob Puchinger, P.-J. Stuckey, M. Wallace, S. Brand

    Research output: Contribution to journalArticlepeer-review

    Abstract

    The G12 project is developing a software environment for stat- ing and solving combinatorial problems by mapping a high-level model of the problem to an efficient combination of solving methods. Model annota- tions 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 annota- tions. The obtained models can then be solved using column generation and branch-and-price. G12 supports the selection of specialised subproblem solvers, the aggregation of identical subproblems reducing symmetries, au- tomatic disaggregation when required by branch-and-bound, the use of spe- cialised subproblem constraint-branching rules, and different master prob- lem solvers including a hybrid solver based on the volume algorithm. We demonstrate the benefits of the G12 framework on three examples: a truck- ing problem, cutting stock, and two-dimensional bin packing.
    Original languageEnglish
    Pages (from-to)77-99
    Number of pages23
    JournalConstraints
    Volume16
    Issue number1
    DOIs
    Publication statusPublished - 2011

    Research Field

    • Former Research Field - Mobility Systems

    Fingerprint

    Dive into the research topics of 'Dantzig-Wolfe Decomposition and Branch-and-Price Solving in G12'. Together they form a unique fingerprint.

    Cite this