×

zbMATH — the first resource for mathematics

Dantzig-Wolfe decomposition and branch-and-price solving in G12. (English) Zbl 1213.90174
Summary: 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.
Reviewer: Reviewer (Berlin)

MSC:
90C05 Linear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T. (2007). Constraint integer programming. PhD thesis, Technische Universität Berlin. · Zbl 1169.90414
[2] Anbil, R., Forrest, J., & Pulleyblank, W. (1998). Column generation and the airline crew pairing problem. In Documenta mathematica, extra volume ICM. · Zbl 0904.90082
[3] Barahona, F., & Anbil, R. (2000). The volume algorithm: Producing primal solutions with a subgradient method. Mathematical Programming, 87(3), 385–399. · Zbl 0961.90058 · doi:10.1007/s101070050002
[4] 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. · Zbl 0979.90092 · doi:10.1287/opre.46.3.316
[5] 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. · Zbl 0993.90011 · doi:10.1023/A:1016059012379
[6] 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.
[7] 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.
[8] Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101–111. · Zbl 0093.32806 · doi:10.1287/opre.8.1.101
[9] Desaulniers, G., Desrosiers, J., & Solomon, M. (Eds.) (2005). Column generation. GERAD 25th Anniversary Series. New York: Springer. · Zbl 1084.90002
[10] 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. · Zbl 1131.68374
[11] ECL i PS e (2009). www.eclipse-clp.org .
[12] Eremin, A. (2003). Using dual values to integrate row and column generation into constraint logic programming. PhD thesis, Imperial College London.
[13] 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.
[14] 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. · Zbl 0918.90117 · doi:10.1016/0377-2217(95)00023-J
[15] Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem (part I). Operations Research, 9, 849–859. · Zbl 0096.35501 · doi:10.1287/opre.9.6.849
[16] 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. · Zbl 1232.90347 · doi:10.1287/mnsc.1040.0332
[17] 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. · Zbl 1147.90416 · doi:10.1002/1097-024X(200009)30:11<1325::AID-SPE342>3.0.CO;2-T
[18] 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. · Zbl 0983.90059
[19] Kantorovich, L. V. (1960). Mathematical methods of organizing and planning production. Management Science, 6(4), 366–422. · Zbl 0995.90532 · doi:10.1287/mnsc.6.4.366
[20] Lodi, A., Martello, S., & Vigo, D. (2004). Models and bounds for two-dimensional level packing problems. Journal of Combinatorial Optimization, 8(3), 363–379. · Zbl 1084.90031 · doi:10.1023/B:JOCO.0000038915.62826.79
[21] Lübbecke, M., & Desrosiers, J. (2005). Selected topics in column generation. Operations Research, 53(6), 1007–1023. · Zbl 1165.90578 · doi:10.1287/opre.1050.0234
[22] Nemhauser, G. L., Savelsbergh, M. W. P., & Sigismondi, G. C. (1994). MINTO, a Mixed INTeger Optimizer. Operations Research Letters, 15, 47–58. · Zbl 0806.90095 · doi:10.1016/0167-6377(94)90013-2
[23] Papadakos, N. (2009). Integrated airline scheduling. Computers and Operations Research, 36, 176–195 (to appear). Available online 27 August 2007. · Zbl 1163.90007 · doi:10.1016/j.cor.2007.08.002
[24] 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. · Zbl 1135.90029 · doi:10.1016/j.ejor.2005.11.064
[25] Ralphs, T., & Ladanyi, L. (2001). COIN/BCP user’s manual.
[26] 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. · Zbl 1062.90007 · doi:10.1023/B:ANOR.0000032576.73681.29
[27] 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.
[28] 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. · Zbl 0877.68015 · doi:10.1016/S0743-1066(96)00068-4
[29] 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. · Zbl 1165.68517
[30] 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.
[31] Van Hentenryck, P., & Michel, L. (2005). Constraint-based local search. Cambridge: MIT. · Zbl 1153.90582
[32] Vanderbeck, F. (2005). Branching in branch-and-price: A generic scheme. Technical Report U-05.14, Applied Mathematics, University Bordeaux 1, France. · Zbl 1229.90100
[33] 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. · Zbl 1091.90052 · doi:10.1007/s10479-005-3455-9
[34] Yunes, T., Aron, I., & Hooker, J. (2009). An integrated solver for optimization problems (updated on 6/10/09). Technical report, University of Miami. · Zbl 1226.90047
[35] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.