×

Constraint programming-based column generation. (English) Zbl 1175.90286

Summary: This paper surveys recent applications and advances of the constraint programming-based column generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by constraint programming (CP). This framework has been introduced to solve crew assignment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using CP are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the CP-based column generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad hoc networks.

MSC:

90C05 Linear programming
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achterberg T (2007) Constraint integer programming. PhD thesis, TU Berlin · Zbl 1169.90414
[2] Apt KR (2003) Principles of constraint programming. Cambridge University Press, Cambridge · Zbl 1187.68132
[3] Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46(3): 316–329 · Zbl 0979.90092
[4] Beldiceanu N, Carlsson M, Rampon JX (2005) Global constraint catalogue. Technical Report SICS-T2005:08, Swedish Institute of Computer Science
[5] Capone A, Carello G, Filippini I, Gualandi S, Malucelli F (2009) Solving a resource allocation problem in wireless mesh networks: a comparison between a CP-based and a classical column generation. Networks (in press) · Zbl 1200.90038
[6] Chu C, Antonio J (1999) Approximation algorithms to solve real-life multicriteria cutting stock problems. Oper Res 47(4): 495–508 · Zbl 1041.90536
[7] Ciriani TA, Colombani Y, Heipcke S (2003) Embedding optimisation algorithms with mosel. 4OR 1(2): 155–167 · Zbl 1097.90036
[8] Demassey S, Pesant G, Rousseau LM (2006) A cost-regular based hybrid column generation approach. Constraints 11(4): 315–333 · Zbl 1117.90066
[9] Desrosiers J, Dumas Y, Solomon MM, Soumis F (1995) Time constrained routing and scheduling. In: Ball MO, Magnanti TL, Monma CL, Nemhauser GL (eds) Network routing. Handbooks in operations research and management science, vol 8. Elsevier, pp 35–139 · Zbl 0861.90052
[10] DIMACS (2002) Graph coloring instances. http://mat.gsia.cmu.edu/COLOR
[11] Easton K, Nemhauser GL, Trick MA (2002) Solving the travelling tournament problem: a combined integer programming and constraint programming approach. In: Proceedings of practice and theory of automated timetabling. Lecture notes in computer science, vol 2740, pp 100–112. Springer, Berlin
[12] Fahle T, Sellmann M (2002) Cost based filtering for the constrained knapsack problem. Ann Oper Res 115(1): 73–93 · Zbl 1013.90105
[13] Fahle T, Junker U, Karisch SE, Kohl N, Sellmann M, Vaaben B (2002) Constraint programming based column generation for crew assignment. J Heuristics 8(1): 59–81 · Zbl 1073.90542
[14] Gabteni S, Grönkvist M (2006) A hybrid column generation and constraint programming optimizer for the tail assignment problem. In: Proceedings of integration of AI and OR techniques in CP for combinatorial optimization. Lecture notes in computer science, vol 3990, pp 89–103. Springer, Berlin · Zbl 1177.90342
[15] Gecode Team (2006) Gecode: generic constraint development environment. http://www.gecode.org
[16] Gendron B, Lebbah H, Pesant G (2005) Improving the cooperation between the master problem and the subproblem in constraint programming based column generation. In: Proceedings of integration of AI and OR techniques in CP for combinatorial optimization. Lecture notes in computer science, vol 3524, pp 217–227. Springer, Berlin · Zbl 1133.68429
[17] Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper Res 9(6): 849–859 · Zbl 0096.35501
[18] Grönkvist M (2004) A constraint programming model for tail assignment. In: Proceedings of integration of AI and OR techniques in CP for combinatorial optimization. Lecture notes in computer science, vol 3011, pp 142–156. Springer, Berlin
[19] Grönkvist M (2006) Accelerating column generation for aircraft scheduling using constraint propagation. Comput OR 33(10): 2918–2934 · Zbl 1086.90023
[20] Gualandi S (2008) Enhancing constraint programming-based column generation for integer programs. PhD thesis, Politecnico di Milano · Zbl 1180.90198
[21] Hansen J, Liden T (2005) Group construction for airline cabin crew: comparing constraint programming with branch and price. In: Proceedings of integration of AI and OR techniques in CP for combinatorial optimization. Lecture notes in computer science, vol 3524, pp 228–242. Springer, Berlin
[22] Harvey WD, Ginsberg ML (1995) Limited discrepancy search. In: Proceedings of international joint conferences on artificial intelligence, pp 607–615
[23] Heisig G, Minner S (1999) ILOG OPL studio. OR Spectr 21(4): 419–427 · Zbl 0947.90500
[24] Junker U, Karisch SE, Kohl N, Vaaben B, Fahle T, Sellmann M (1999) A framework for constraint programming based column generation. In: Proceedings of principles and practice of constraint programming. Lecture notes in computer science, vol 1713, pp 261–274. Springer, Berlin · Zbl 0983.90059
[25] Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper Res 53(6): 1007–1023 · Zbl 1165.90578
[26] Marriott K, Nethercote N, Rafeh R, Stuckey PJ, De La Banda MG, Wallace M. (2008) The design of the Zinc modelling language. Constraints 13(3): 229–267 · Zbl 1146.68352
[27] Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, New York · Zbl 0708.68002
[28] Mehrotra A, Trick MA (1996) A column generation approach for graph coloring. J Comput 8(4): 344–354 · Zbl 0884.90144
[29] Michel L, Van Hentenryck P (2003) Comet in context. In: Proceedings of the Paris C. Kanellakis memorial workshop on Principles of computing & knowledge, pp 95–107. ACM, New York
[30] Milano M, Wallace M (2006) Integrating operations research in constraint programming. 4OR 4(3): 1–45 · Zbl 1125.90392
[31] Pisinger D, Sigurd M (2007) Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. J Comput 19(1): 36–51 · Zbl 1241.90118
[32] Puchinger J, Stuckey PJ, Wallace M, Brand S (2008) From high-level model to branch-and-price solution in G12. In: Proceedings of integration of AI and OR techniques in CP for combinatorial optimization. Lecture notes in computer science, vol 5015, pp 218–232. Springer, Berlin · Zbl 1142.90503
[33] Ralphs TK, Ladanyi L (2001) COIN/BCP User’s Manual
[34] Régin JC (2002) Cost-based arc consistency for global cardinality constraints. Constraints 7(3): 387–405 · Zbl 1028.68157
[35] Rossi F, Van Beek P, Walsh T (2006) Handbook of constraint programming. Elsevier Science, Amsterdam · Zbl 1175.90011
[36] Rousseau LM (2004) Stabilization issues for constraint programming based column generation. In: Proceedings of integration of AI and OR techniques in CP for combinatorial optimization. Lecture notes in computer science, vol 3011, pp 402–408. Springer, Berlin
[37] Rousseau LM, Gendreau M, Pesant G, Focacci F (2004) Solving VRPTWs with constraint programming based column generation. Ann Oper Res 130(1): 199–216 · Zbl 1062.90007
[38] Rousseau LM, Gendreau M, Feillet D (2007) Interior point stabilization for column generation. Oper Res Lett 35(5): 660–668 · Zbl 1149.90099
[39] Sadykov R, Wolsey LA (2006) Integer programming and constraint programming in solving a multimachine assignment scheduling problem with deadlines and release dates. J Comput 18(2): 209–217 · Zbl 1241.90056
[40] Sellmann M, Zervoudakis K, Stamatopoulos P, Fahle T (2002) Crew assignment via constraint programming: integrating column generation and heuristic tree search. Ann Oper Res 115(1): 207–225 · Zbl 1013.90091
[41] Wolsey LA (1998) Integer programming. Wiley, New York · Zbl 0930.90072
[42] Yunes TH, Moura AV, de Souza CC (2000) Solving very large crew scheduling problems to optimality. In: Proceedings of ACM symposium on Applied computing, vol 1, pp 446–451. ACM, New York
[43] Yunes TH, Moura AV, de Souza CC (2005) Hybrid column generation approaches for urban transit crew management problems. Transp Sci 39(2): 273–288
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.