Abstract
Constraint Programming (CP) offers a rich modeling language of constraints embedding efficient algorithms to handle complex and heterogeneous combinatorial problems. To solve hard combinatorial optimization problems using CP alone or hybrid CP-ILP decomposition methods, costs also have to be taken into account within the propagation process. Optimization constraints, with their cost-based filtering algorithms, aim to apply inference based on optimality rather than feasibility. This paper introduces a new optimization constraint, cost-regular. Its filtering algorithm is based on the computation of shortest and longest paths in a layered directed graph. The support information is also used to guide the search for solutions. We believe this constraint to be particularly useful in modeling and solving Column Generation subproblems and evaluate its behaviour on complex Employee Timetabling Problems through a flexible CP-based column generation approach. Computational results on generated benchmark sets and on a complex real-world instance are given.
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
Baptiste, P., Le Pape C., & Peridy L. (1998). Global constraints for partial CSPs: A case-study of resource and due date constraints. Constraints, 87–102.
Barnhart, C., Johnson, L., Nemhauser, G., Savelsbergh, M., & Vance, P. (1998). Branch-and-Price: Column generation for solving huge integer programs. Operations Research, 46, 316–329.
Beldiceanu, N., Carlsson, M., & Thiel, S. (2002). Cost-filtering algorithms for the two sides of the Sum of the weights of distinct values constraint. Technical Report SICS T2002:14.
Caseau, Y., & Laburthe, F. (1997). Solving various weighted matching problems with constraints. In Proceedings Of The 3rd International Conference on Principles and Practice of Constraint Programming—CP’97 LNCS 1330 (pp.17–31). Berlin Heidelberg New York: Springer.
Chvátal, V. (1983). Linear Programming. New York: Freeman.
Dantzig, G. (1954). A comment on Edie’s traffic delays at toll booths. Operations Research, 2, 339–341.
Demassey, S., Pesant, G., & Rousseau, L.-M. (2005). Constraint programming based column generation for employee timetabling. In Proceedings of 2nd International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems—CPAIOR’05 LNCS 3524 (pp.140–154). Berlin Heidelberg New York: Springer.
Desrosiers, J., Dumas, Y., Solomon, M.M., & Soumis, F. (1995). Time constrained routing and scheduling. In M.O. Ball, T.L. Magnanti, C.L. Monna & G.I. Nemhauser (Eds.), Network Routing, Handbooks in Operations Research and Management Science (pp.35–139).
Ernst, A.T., Jiang, H., Krishnamoorthy, M., Owens, B., & Sier, D. (2004). An annotated bibliography of personnel scheduling and rostering. Annals of Operations Research, 127, 21–144.
Ernst, A.T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153, 3–27.
Fahle, T., Junker, U., Karisch, S.E., Kohl, N., Vaaben, B. & Sellmann, M. (2002). Constraint programming based column generation for crew assignment. Journal of Heuristics, 8, 59–81.
Fahle, T., & Sellmann, M. (2002). Cost based filtering for the constrained knapsack problem. Annals of Operations Research, 115, 73–93.
Focacci, F., Lodi, A., & Milano, M. (1999). Cost-based domain filtering. In Proceedings of 5th International Conference on Principles and Practice of Constraint Programming—CP’99 LNCS 1713, (pp.189–203). Berlin Heidelberg New York: Springer.
Focacci, F., Lodi, A. & Milano, M. (2002). Optimization-oriented global constraints. Constraints, 7, 351–365.
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 2nd Internationl Conference on Integration of AI And OR Techniques in Constraint Programming for Combinatorial Optimization Problems—CPAIOR’05 LNCS 3524 (pp.217–227). Berlin Heidelberg New York: Springer.
Junker, U., Karish, S.E., Kohl, N., Vaaben, N., Fahle, T., & Sellmann, M. (1999). A framework for constraint programming based column generation. In Proceedings of 5th International Conference on Principles and Practice of Constraint Programming—CP’99 LNCS 1713 (pp.261–274). Berlin Heidelberg New York: Springer.
Ottosson, G., & Thorsteinsson, E.S. (2000). Linear relaxation and reduced-cost based propagation of continuous variable subscripts. In Proceedings of International Workshop on Integration of AI and OR Techniques in Constraint Programming For Combinatorial Optimization Problems—CPAIOR’00 (pp.129–138). Paderborn Center for Parallel Computing, Technical Report tr-001-2000.
Pesant G. (2004). A regular language membership constraint for finite sequences of variables. In Proceedings of 10th International Conference on Principles and Practice of Constraint Programming—CP’04 LNCS 3258 (pp.482–495). Berlin Heidelberg New York: Springer.
Petit, T., Régin, J.-C., & Bessière, C. (2001). Specific filtering algorithms for over constrained problems. In Proceedings of 7th International Conference on Principles and Practice of Constraint Programming—CP’01 LNCS (pp.451–463). Berlin Heidelberg New York: Springer.
Régin J.-C. (1996). Generalized arc consistency for global cardinality constraints. In Proceedings of AAAI’96 (pp.209–215). Cambridge, Massachusetts: MIT.
Régin J.-C. (2002). Cost-based arc consistency for global cardinality constraints. Constraints, 7, 387–405.
Rousseau, L.-M., Gendreau, M., Pesant, G., & Focacci, F. (2004). Solving VRPTWs with constraint programming based column generation. Annals of Operations Research, 130, 199–216
Sellmann, M., Zervoudakis, K., Stamatopoulos, P., & Fahle, T. (2002). Crew assignment via constraint programming: integrating column generation and heuristic tree search. Annals of Operations Research, 115, 207–225.
Sellmann, M. (2002). An arc-consistency algorithm for the minimum weight all different constraint. In Proceedings of 8th International Conference on Principles and Practice of Constraint Programming—CP’02 LNCS 2470 (pp.744–749). Berlin Heidelberg New York: Springer.
Sellmann, M. (2003). Cost-based filtering for shorter path constraints. In Proceedings of 9th International Conference on Principles and Practice of Constraint Programming—CP’03 LNCS 2833, (pp.694–708). Berlin Heidelberg New York: Springer.
Sellmann, M. (2004). Theoretical foundations of CP-based Lagrangian relaxation. In Proceedings of 10th Internatioanl Conference on Principles and Practice of Constraint Programming—CP’04 LNCS 3258, (pp.634–647). Berlin Heidelberg New York: Springer.
van Hoeve, W.-J., Pesant, G., & Rousseau, L.-M. (2006). On global warming: flow based soft constraints. Journal of Heuristics 12(4–5), 347–373.
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper appeared as [7]. This research was supported by the Mathematics of Information Technology and Complex Systems (MITACS) Internship program in association with Omega Optimisation Inc. (CA).
Rights and permissions
About this article
Cite this article
Demassey, S., Pesant, G. & Rousseau, LM. A Cost-Regular Based Hybrid Column Generation Approach. Constraints 11, 315–333 (2006). https://doi.org/10.1007/s10601-006-9003-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-006-9003-7