Abstract
This paper presents Constraint Programming as a natural formalism for modelling problems, and as a flexible platform for solving them. CP has a range of techniques for handling constraints including several forms of propagation and tailored algorithms for global constraints. It also allows linear programming to be combined with propagation and novel and varied search techniques which can be easily expressed in CP. The paper describes how CP can be used to exploit linear programming within different kinds of hybrid algorithm. In particular it can enhance techniques such as Lagrangian relaxation, Benders decomposition and column generation.
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. (2009). Scip: solving constraint integer programs. Mathematical Programming Computation.
Achterberg, T., Berthold, T., Koch, T., & Wolter, K. (2008). Constraint integer programming: a new approach to integrate cp and mip. In Proceedings of the intl conference on the integration of AI and OR techniques in constraint programming, 2008, pp. 6–20.
Ahmed, S., & Shapiro, A. (2002). The sample average approximation method for stochastic programs with integer recourse. In Optimization on line, 2002.
Applegate, D., Bixby, R., Chvátal, V., & Cook, W. (1999). Tsp-solver concorde. http://www.keck.caam.rice.edu/concorde.html.
Apt, K. R., & Wallace, M. G. (2006). Constraint logic programming using ECLiPSe. Cambridge: Cambridge University Press.
Arbab, F., & Monfroy, E. (1998). Coordination of heterogeneous distributed cooperative constraint solving. Applied Computing Review, 6, 4–17. ACM SIGAPP.
Baptiste, P., Le Pape, C., & Nuijten, W. (1995). Efficient operations research algorithms in constraint-based scheduling. In 1st Joint workshop on artificial intelligence and operational research.
Baptiste, P., Le Pape, C., & Nuijten, W. (2003). Constraint-based scheduling. Dordrecht: Kluwer Academic Publisher.
Beldiceanu, N., & Carlsson, M. (2002). A new multi-resource cumulatives constraint with negative heights. In LNCS : Vol. 2470. Proc. of the Int. Conference on Principles and Practice of Constraint Programming CP 2002 (pp. 63–79). Berlin: Springer.
Beldiceanu, N., Bourreau, E., Chan, P., & Rivreau, D. (1997). Partial search strategy in CHIP. In Proceedings of the 2nd international conference on meta-heuristics, 1997.
Beldiceanu, N., Carlsson, M., & Rampon, J.-X. (2005). Global constraint catalog (SICS Technical Report T2005:08).
Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4, 238–252.
Benhamou, F., Granvilliers, L., & Goualard, F. (1999). Interval constraints: results and perspectives. In New Trends in Constraints (pp. 1–16).
Beringer, H., & De Backer, B. (1995). Combinatorial problem solving in constraint logic programming with cooperating solvers. In C. Beierle & L. Plümer (Eds.), Logic programming: formal methods and practical applications (pp. 245–272). Amsterdam: North Holland.
Bèssiere, C., & Régin, J. C. (1997). Arc consistency for general constraint networks: preliminary results. In M. Pollack (Ed.), Proceedings of the international joint conference on artificial intelligence, IJCAI (pp. 398–404). San Mateo: Morgan Kaufmann.
Bousonville, T., Focacci, F., Le Pape, C., Nuijten, E., Paulin, F., Puget, J. F., Robert, A., & Sadeghin, A. (2005). Integration of rules and optimization in plant powerops. In R. Bartak & M. Milano (Eds.), LNCS : Vol. 3524. Proc. of the international conference in the integration of AI and OR techniques in constraint programming—CPAIOR 2005 (pp. 1–15). Berlin: Springer.
Carlier, J., & Pinson, E. (1995). An algorithm for solving job shop scheduling. Management Science, 35, 164–176.
Cheng, B. M. W., Lee, J. H. M., & Wu, J. C. K. (1996). Speeding up constraint propagation by redundant modeling. In E. C. Freuder (Ed.), LNCS : Vol. 1118. Proc. of the int. conference on principles and practice of constraint programming (pp. 91–103). Berlin: Springer.
Choi, C. W., Harvey, W., Ho-Man Lee, J., & Stuckey, P. J. (2004). Finite domain bounds consistency revisited. URL www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cs/0412021.
Codognet, P., & Diaz, D. (1996). Compiling constraints in clp(fd). Journal of Logic Programming, 27, 1–199.
COIN-OR Foundation (2009). COmputational INfrastructure for Operations Research. http://www.coin-or.org/.
Cordier, C., Marchand, H., Laundy, R., & Wolsey, L. A. (1999). BC-Opt: a branchand-cut code for mixed integer programs. Mathematical Programming, 86(2), 335–354.
Crainic, T. G., Gendreau, M., & Farvolden, J. M. (2000). A simplex-based tabu search method for capacitated network design. INFORMS Journal of Computing, 12(3), 223–236.
Davis, E. (1987). Constraint propogation with interval labels. Artificial Intelligence, 32(3), 281–331.
Demassey, S., Pesant, G., & Rousseau, L.-M. (2005). Constraint programming based column generation for employee timetabling. In R. Bartak & M. Milano (Eds.), LNCS : Vol. 3524. Proc. of the int. conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems—CPAIOR (pp. 140–154). Berlin: Springer.
Deransart, P., Hermenegildo, M. V., & Maluszynski, J. (2000). In LNCS : Vol. 1870. Analysis and visualisation tools for constraint programming. Berlin: Springer.
El Sakkout, H., & Wallace, M. (2000). Probe backtrack search for minimal perturbation in dynamic scheduling. Constraints, 5(4), 359–388.
Fahle, T., Junker, U., Karisch, S. E., Kohl, N., Sellmann, M., & Vaaben, B. (2002). Constraint programming based column generation for crew assignment. Journal of Heuristics, 8(1), 59–81.
Focacci, F., Lodi, A., & Milano, M. (1999). Cost-based domain filtering. In J. Jaffar (Ed.), LNCS : Vol. 1713. Proceedings of the international conference on principles and practice of constraint programming CP’99 (pp. 189–203). Berlin: Springer.
Focacci, F., Laburthe, F., & Lodi, A. (2003). Local search and constraint programming—ls and cp illustrated on a transportation problem. In M. Milano (Ed.), Constraint and integer programming—toward a unified methodology, Chap. 9. Dordrecht: Kluwer Academic Publisher.
Freuder, E., & Régin, J. C. (1999). Using constraint metaknowledge to reduce arc-consistency computation. Artificial Intelligence, 107, 125–148.
Fruhwirth, T. (1998). Theory and practice of constraint handling rules. Journal of Logic Programming—Special Issue on Constraint Logic Programming, 37.
Gendron, B., Lebbah, H., & Pesant, G. (2005). Improving the cooperation between the master problem and the subproblem in constraint programming based column generation. In R. Bartak & M. Milano (Eds.), LNCS : Vol. 3524. Proc. of the int. conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems—CPAIOR (pp. 217–227). Berlin: Springer.
Grossmann, I. E., & Jain, V. (2001). Algorithms for hybrid milp/cp models for a class of optimization problems. INFORMS Journal on Computing, 13, 258–276.
Guret, C., Prins, C., & Sevaux, M. (2002). Application of optimization with Xpress MP. In Dash optimization. ISBN 0-9543503-0-8.
Harvey, W. D., & Ginsberg, M. L. (1995). Limited discrepancy search. In C. S. Mellish (Ed.), Proceedings of the fourteenth international joint conference on artificial intelligence (IJCAI-95) (Vol. 1, pp. 607–615).
Hooker, J. N. (2004). A hybrid method for planning and scheduling. In M. Wallace (Ed.), LNCS : Vol. 3258. Proc. of the int. conference on principles and practice of constraint programming—CP 2004 (pp. 305–316). Berlin: Springer.
Hooker, J. N. (2005). Planning and scheduling to minimize tardiness. In P. Van Beek (Ed.), LNCS : Vol. 3709. Proc. of the int. conference on principles and practice of constraint programming—CP 2005 (pp. 314–327). Berlin: Springer.
Hooker, J. N., & Ottosson, G. (2003). Logic-based benders decomposition. Mathematical Programming, 96, 33–60.
ILOG Optimization Team (2003). Concert technology.
ILOG Optimization Team (2008). Cplex 11.2 user manual.
Junger, 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, 1325–1352.
Kamarainen, O., & El Sakkout, H. (2002). Local probing applied to scheduling. In P. Van Hentenryck (Ed.), LNCS : Vol. 2470. Proc. of the int. conference on principles and practice of constraint programming (pp. 155–171). Berlin: Springer.
Laburthe, F., & Caseau, Y. (2002). Salsa: a language for search algorithms. Constraints, 7(3–4), 255–288.
Lamaréchal, C. (2003). The omnipresence of Lagrange. 4OR, 1, 7–25.
Langley, P. (1992). Systematic and nonsystematic search strategies. In J. Hendler (Ed.), Proceedings of the 1st international conference on AI planning systems, AIPS (pp. 145–152). San Mateo: Morgan Kaufmann.
Laporte, G., & Louveaux, F. V. (1993). The integer l-shaped method for stochastic integer programs with complete recourse. Operations Research Letters, 13, 133–142.
Laurière, J. L. (1978). A language and a program for stating and solving combinatorial problems. Artificial Intelligence, 10, 29–127.
Le Provost, T., & Wallace, M. (1993). Generalized constraint propagation over the clp scheme. Journal of Logic Programming, 16, 319–359.
Lhomme, O. & Jussien, N. (2002). Local search with constraint propagation and conflict-based heuristics. Artificial Intelligence, 139(1), 21–45.
Lin, S., & Kernighan, B. (1973). An efficient heuristic for the Traveling Salesman Problem. Operations Research, 21(2), 498–516.
Marques-Silva, J. P., & Sakallah, K. A. (1999). Grasp-a search algorithm for propositional satisfiability. IEEE Transactions on Computers, 48(5), 506–521.
Marriott, K., Nethercote, N., Rafeh, R., Stuckey, P. J., Garcia De La Banda, M., & Wallace, M. (2008). The design of the zinc modelling language. Constraints, 13(3), 229–267.
Michel, L., & Van Hentenryck, P. (2000). Localizer. Constraints, 5(1–2), 43–84.
Milano, M., & Wallace, M. (2005). Integrating operations research in constraint programming. 4OR, 4(3), 175–219.
Moura, A. V., Yunes, T. H., & de Souza, C. C. (2005). Hybrid column generation approaches for urban transit crew management problems. Transportation Science, 39(2), 273–288.
Norkin, V. I., Pflug, G. C., & Ruszczynski, A. (1998). A branch and bound method for stochastic global optimization. Mathematical Programming, 83, 407–423.
Nowicki, E., & Smutnicki, C. (1996). A fast taboo search algorithm for the job shop problem. Management Science, 42(6), 797–813.
Ohrimenko, O., Stuckey, P. J., & Codish, M. (2009). Propagation via lazy clause generation. Constraints, 14(3), 357–391.
Ouaja, W., & Richards, B. (2005). Hybrid Lagrangian relaxation for bandwidth-constrained routing: knapsack decomposition. In Proceedings of 2005 ACM symposium on applied computing (pp. 383–387).
Perron, L., Shaw, P., & Furnon, V. (2004). Propagation guided large neighborhood search. In M. Wallace (Ed.), LNCS : Vol. 3258. Proc. of the int. conference on principles and practice of constraint programming CP2004. (pp. 468–481). Berlin: Springer.
Pesant, G., & Gendreau, M. (1999). A constraint programming framework for local search methods. Journal of Heuristics, 5(3), 255–279.
Puchinger, J., Stuckey, P. J., Wallace, M., & Brand, S. (2008). From high-level model to branch-and-price solution in g12. In Proceedings of the intl conference on the integration of artificial intelligence and operations research techniques in CP (pp. 218–232).
Refalo, P. (2000). Linear formulation of constraint programming models and hybrid solvers. In R. Dechter (Ed.), LNCS : Vol. 1894. Proceedings of the international conference on principle and practice of constraint programming—CP 2000. Berlin: Springer.
Régin, J. C. (1994). A filtering algorithm for constraints of difference in CSPs. In B. Hayes-Roth & R. Korf (Eds.), Proceedings of the twelfth national conference on artificial intelligence—AAAI94 (pp. 362–367).
Régin, J. C. (1999). Arc consistency for global cardinality constraints with costs. In J. Jaffar (Ed.), LNCS : Vol. 1713. Proceedings of the international conference on principles and practice of constraint programming, CP’99 (pp. 390–404). Berlin: Springer.
Regin, J. C. (2004). Global constraints and filtering algorithms. In M. Milano (Ed.), Constraint and integer programming. Dordrecht: Kluwer Academic Publisher.
Rodosek, R., Wallace, M., & Hajian, M. T. (1997). A new approach to integrating mixed integer programming and constraint logic programming. Annals of Operational Research. Recent Advances in Combinatorial Optimization.
Sannella, M., Maloney, J., Freeman-Benson, B., & Borning, A. (1993). Multi-way versus one-way constraints in user interfaces: experience with the DeltaBlue algorithm. Software: Practice and Experience, 23(5), 529–566.
Schulte, C., & Stuckey, P. J. (2005). When do bounds and domain propagation lead to the same search space. ACM Transactions on Programming Languages and Systems, 27(3), 388–425.
Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In M. Maher & J. F. Puget (Eds.), LNCS : Vol. 1520. Proc. of the int. conference on principles and practice of constraint programming CP1998 (pp. 417–431). Berlin: Springer.
Tarim, A., Manandhar, S., & Walsh, T. (2006). Stochastic constraint programming: a scenario-based approach. Constraints, 11, 53–80.
Van Hentenryck, P. (1999). The OPL optimization programming language. Cambridge: MIT Press.
Van Hentenryck, P., & Michel, L. (2005). Constraint-based local search. Cambridge: MIT Press.
van Hoeve, W. J. (2006). The alldifferent constraint: a systematic overview. URL www.cs.cornell.edu/~vanhoeve/papers/alldiff.pdf.
Walsh, T. (2002). Stochastic constraint programming. In F. van Harmelen (Ed.), Proc. of the European conference on artificial intelligence, ECAI. Amsterdam: IOS Press.
Zhou, N. F. (2005). Finite-domain constraint propagators in action rules. Theory and Practice of Logic Programming (4–5).
Author information
Authors and Affiliations
Corresponding author
Additional information
This is an updated version of the paper that appeared in 4OR, 4(3), 175–219 (2005).
Rights and permissions
About this article
Cite this article
Milano, M., Wallace, M. Integrating Operations Research in Constraint Programming. Ann Oper Res 175, 37–76 (2010). https://doi.org/10.1007/s10479-009-0654-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-009-0654-9