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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Achterberg, T. (2007). Constraint integer programming. PhD thesis, Technische Universität Berlin.
Anbil, R., Forrest, J., & Pulleyblank, W. (1998). Column generation and the airline crew pairing problem. In Documenta mathematica, extra volume ICM.
Barahona, F., & Anbil, R. (2000). The volume algorithm: Producing primal solutions with a subgradient method. Mathematical Programming, 87(3), 385–399.
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316–329.
Boland, N., & Surendonk, T. (2001). A column generation approach to delivery planning over time with inhomogeneous service providers and service interval constraints. Annals of Operations Research, 108, 143–156.
Brand, S., Duck, G. J., Puchinger, J., & Stuckey, P. J. (2008). Flexible, rule-based constraint model linearisation. In P. Hudak, & D. Warren (Eds.), Practical aspects of declarative languages (PADL’08). LNCS (Vol. 4902, pp. 68–83). New York: Springer.
Chabrier, A. (2002). Génération de colonnes et de coupes utilisant des sous-problèmes de plus court chemin. PhD thesis, Université d’Angers, France.
Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101–111.
Desaulniers, G., Desrosiers, J., & Solomon, M. (Eds.) (2005). Column generation. GERAD 25th Anniversary Series. New York: Springer.
Duck, G. J., Stuckey, P. J., & Brand, S. (2006). ACD term rewriting. In S. Etalle, & M. Truszczynski (Eds.), Logic programming (ICLP 2006). LNCS (Vol. 4079, pp. 117–131). New York: Springer.
ECLiPSe (2009). www.eclipse-clp.org.
Eremin, A. (2003). Using dual values to integrate row and column generation into constraint logic programming. PhD thesis, Imperial College London.
Garcia de la Banda, M. J., Marriott, K., Rafeh, R., & Wallace, M. (2006). The modelling language Zinc. In F. Benhamou (Ed.), Principles and practice of constraint programming (CP’06). LNCS (Vol. 4204, pp. 700–705). New York: Springer.
Gau, T., & Wäscher, G. (1995). CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem. European Journal of Operational Research, 84(3), 572–579.
Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem (part I). Operations Research, 9, 849–859.
Gunluk, O., Ladanyi, L., & Vries, S. D. (2005). A branch-and-price algorithm and new test problems for spectrum auctions. Management Science, 51(3), 391–406.
Jünger, M., & Thienel, S. (2000). The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization. Software: Practice and Experience, 30(11), 1325–1352.
Junker, U., Karisch, S. E., Kohl, N., Vaaben, B., Fahle, T., & Sellmann, M. (1999). A framework for constraint programming based column generation. In J. Jaffar (Ed.), Principles and practice of constraint programming (CP’99). LNCS (Vol. 1713, pp. 261–274). New York: Springer.
Kantorovich, L. V. (1960). Mathematical methods of organizing and planning production. Management Science, 6(4), 366–422.
Lodi, A., Martello, S., & Vigo, D. (2004). Models and bounds for two-dimensional level packing problems. Journal of Combinatorial Optimization, 8(3), 363–379.
Lübbecke, M., & Desrosiers, J. (2005). Selected topics in column generation. Operations Research, 53(6), 1007–1023.
Nemhauser, G. L., Savelsbergh, M. W. P., & Sigismondi, G. C. (1994). MINTO, a Mixed INTeger Optimizer. Operations Research Letters, 15, 47–58.
Papadakos, N. (2009). Integrated airline scheduling. Computers and Operations Research, 36, 176–195 (to appear). Available online 27 August 2007.
Puchinger, J., & Raidl, G. R. (2007). Models and algorithms for three-stage two-dimensional bin packing. European Journal of Operational Research, 183(3), 1304–1327.
Ralphs, T., & Ladanyi, L. (2001). COIN/BCP user’s manual.
Rousseau, L.-M., Gendreau, M., Pesant, G., & Focacci, F. (2004). Solving VRPTWs with constraint programming based column generation. Annals of Operations Research, 130(1), 199–216.
Ryan, D. M., & Foster, B. (1981). An integer programming approach to scheduling. In A. Wren (Ed.), Computer scheduling of public transport urban passenger vehicle and crew scheduling (pp. 269–280). Amsterdam: North Holland.
Somogyi, Z., Henderson, F., & Conway, T. (1996). The execution algorithm of Mercury, an efficient purely declarative logic programming language. Journal of Logic Programming, 29(1–3), 17–64.
Stuckey, P. J., de la Banda, M. J. G., Maher, M. J., Marriott, K., Slaney, J. K., Somogyi, Z., et al. (2005). The G12 project: Mapping solver independent models to efficient solutions. In P. van Beek (Ed.), Principles and practice of constraint programming (CP’05). LNCS (Vol. 3709, pp. 13–16). New York: Springer.
Van Hentenryck, P., & Michel, L. (1999). OPL script: Composing and controlling models. In K. R. Apt, A. C. Kakas, E. Monfroy, & F. Rossi (Eds.), New trends in constraints. LNCS (Vol. 1865, pp. 75–90). New York: Springer.
Van Hentenryck, P., & Michel, L. (2005). Constraint-based local search. Cambridge: MIT.
Vanderbeck, F. (2005). Branching in branch-and-price: A generic scheme. Technical Report U-05.14, Applied Mathematics, University Bordeaux 1, France.
Villeneuve, D., Desrosiers, J., Lübbecke, M. E., & Soumis, F. (2005). On compact formulations for integer programs solved by column generation. Annals of Operations Research, 139(1), 375–388.
Yunes, T., Aron, I., & Hooker, J. (2009). An integrated solver for optimization problems (updated on 6/10/09). Technical report, University of Miami.
Yunes, T. H., Moura, A. V., & de Souza, C. C. (2000). A hybrid approach for solving large scale crew scheduling problems. In Practical aspects of declarative languages (PADL’00). LNCS (Vol. 1753, pp. 293–207). New York: Springer.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Puchinger, J., Stuckey, P.J., Wallace, M.G. et al. Dantzig-Wolfe decomposition and branch-and-price solving in G12. Constraints 16, 77–99 (2011). https://doi.org/10.1007/s10601-009-9085-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-009-9085-0