×

zbMATH — the first resource for mathematics

Integrating operations research in constraint programming. (English) Zbl 1185.90189
Summary: 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.

MSC:
90C30 Nonlinear programming
90C05 Linear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T. (2009). Scip: solving constraint integer programs. Mathematical Programming Computation. · Zbl 1171.90476
[2] 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. · Zbl 1142.68504
[3] Ahmed, S., & Shapiro, A. (2002). The sample average approximation method for stochastic programs with integer recourse. In Optimization on line, 2002.
[4] Applegate, D., Bixby, R., Chvátal, V., & Cook, W. (1999). Tsp-solver concorde. http://www.keck.caam.rice.edu/concorde.html .
[5] Apt, K. R., & Wallace, M. G. (2006). Constraint logic programming using ECLiPSe. Cambridge: Cambridge University Press.
[6] Arbab, F., & Monfroy, E. (1998). Coordination of heterogeneous distributed cooperative constraint solving. Applied Computing Review, 6, 4–17. ACM SIGAPP. · doi:10.1145/297114.297115
[7] 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. · Zbl 1094.90002
[8] Baptiste, P., Le Pape, C., & Nuijten, W. (2003). Constraint-based scheduling. Dordrecht: Kluwer Academic Publisher. · Zbl 1094.90002
[9] 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.
[10] 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.
[11] Beldiceanu, N., Carlsson, M., & Rampon, J.-X. (2005). Global constraint catalog (SICS Technical Report T2005:08).
[12] Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4, 238–252. · Zbl 0109.38302 · doi:10.1007/BF01386316
[13] Benhamou, F., Granvilliers, L., & Goualard, F. (1999). Interval constraints: results and perspectives. In New Trends in Constraints (pp. 1–16).
[14] 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. · Zbl 0939.68580
[15] 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.
[16] 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. · Zbl 1133.90329
[17] Carlier, J., & Pinson, E. (1995). An algorithm for solving job shop scheduling. Management Science, 35, 164–176. · Zbl 0677.90036 · doi:10.1287/mnsc.35.2.164
[18] 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.
[19] 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 .
[20] Codognet, P., & Diaz, D. (1996). Compiling constraints in clp(fd). Journal of Logic Programming, 27, 1–199. · Zbl 0874.68054 · doi:10.1016/0743-1066(95)00121-2
[21] COIN-OR Foundation (2009). COmputational INfrastructure for Operations Research. http://www.coin-or.org/ .
[22] 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. · Zbl 0939.90025 · doi:10.1007/s101070050092
[23] 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. · Zbl 1040.90506 · doi:10.1287/ijoc.12.3.223.12638
[24] Davis, E. (1987). Constraint propogation with interval labels. Artificial Intelligence, 32(3), 281–331. · Zbl 0642.68176 · doi:10.1016/0004-3702(87)90091-9
[25] 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. · Zbl 1133.90359
[26] Deransart, P., Hermenegildo, M. V., & Maluszynski, J. (2000). In LNCS : Vol. 1870. Analysis and visualisation tools for constraint programming. Berlin: Springer.
[27] El Sakkout, H., & Wallace, M. (2000). Probe backtrack search for minimal perturbation in dynamic scheduling. Constraints, 5(4), 359–388. · Zbl 0970.68014 · doi:10.1023/A:1009856210543
[28] 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. · Zbl 1073.90542 · doi:10.1023/A:1013613701606
[29] 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.
[30] 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. · Zbl 1140.90330
[31] Freuder, E., & Régin, J. C. (1999). Using constraint metaknowledge to reduce arc-consistency computation. Artificial Intelligence, 107, 125–148. · Zbl 0911.68192 · doi:10.1016/S0004-3702(98)00105-2
[32] Fruhwirth, T. (1998). Theory and practice of constraint handling rules. Journal of Logic Programming–Special Issue on Constraint Logic Programming, 37.
[33] 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. · Zbl 1133.68429
[34] 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. · Zbl 1238.90106 · doi:10.1287/ijoc.13.4.258.9733
[35] Guret, C., Prins, C., & Sevaux, M. (2002). Application of optimization with Xpress MP. In Dash optimization. ISBN 0-9543503-0-8.
[36] 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).
[37] 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. · Zbl 1152.90445
[38] 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. · Zbl 1153.90423
[39] Hooker, J. N., & Ottosson, G. (2003). Logic-based benders decomposition. Mathematical Programming, 96, 33–60. · Zbl 1023.90082
[40] ILOG Optimization Team (2003). Concert technology.
[41] ILOG Optimization Team (2008). Cplex 11.2 user manual.
[42] 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. · Zbl 1147.90416 · doi:10.1002/1097-024X(200009)30:11<1325::AID-SPE342>3.0.CO;2-T
[43] 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. · Zbl 1094.68646
[44] Laburthe, F., & Caseau, Y. (2002). Salsa: a language for search algorithms. Constraints, 7(3–4), 255–288. · Zbl 1020.68028 · doi:10.1023/A:1020565317875
[45] Lamaréchal, C. (2003). The omnipresence of Lagrange. 4OR, 1, 7–25. · Zbl 1046.90064
[46] 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.
[47] Laporte, G., & Louveaux, F. V. (1993). The integer l-shaped method for stochastic integer programs with complete recourse. Operations Research Letters, 13, 133–142. · Zbl 0793.90043 · doi:10.1016/0167-6377(93)90002-X
[48] Laurière, J. L. (1978). A language and a program for stating and solving combinatorial problems. Artificial Intelligence, 10, 29–127. · Zbl 0374.68060 · doi:10.1016/0004-3702(78)90029-2
[49] Le Provost, T., & Wallace, M. (1993). Generalized constraint propagation over the clp scheme. Journal of Logic Programming, 16, 319–359. · Zbl 0783.68025 · doi:10.1016/0743-1066(93)90047-K
[50] Lhomme, O. & Jussien, N. (2002). Local search with constraint propagation and conflict-based heuristics. Artificial Intelligence, 139(1), 21–45. · Zbl 1015.68056 · doi:10.1016/S0004-3702(02)00221-7
[51] Lin, S., & Kernighan, B. (1973). An efficient heuristic for the Traveling Salesman Problem. Operations Research, 21(2), 498–516. · Zbl 0256.90038 · doi:10.1287/opre.21.2.498
[52] Marques-Silva, J. P., & Sakallah, K. A. (1999). Grasp-a search algorithm for propositional satisfiability. IEEE Transactions on Computers, 48(5), 506–521. · Zbl 01935259 · doi:10.1109/12.769433
[53] 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. · Zbl 1146.68352 · doi:10.1007/s10601-008-9041-4
[54] Michel, L., & Van Hentenryck, P. (2000). Localizer. Constraints, 5(1–2), 43–84. · Zbl 0988.90015 · doi:10.1023/A:1009818401322
[55] Milano, M., & Wallace, M. (2005). Integrating operations research in constraint programming. 4OR, 4(3), 175–219. · Zbl 1125.90392 · doi:10.1007/s10288-006-0019-z
[56] 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. · doi:10.1287/trsc.1030.0078
[57] Norkin, V. I., Pflug, G. C., & Ruszczynski, A. (1998). A branch and bound method for stochastic global optimization. Mathematical Programming, 83, 407–423.
[58] Nowicki, E., & Smutnicki, C. (1996). A fast taboo search algorithm for the job shop problem. Management Science, 42(6), 797–813. · Zbl 0880.90079 · doi:10.1287/mnsc.42.6.797
[59] Ohrimenko, O., Stuckey, P. J., & Codish, M. (2009). Propagation via lazy clause generation. Constraints, 14(3), 357–391. · Zbl 1192.68654 · doi:10.1007/s10601-008-9064-x
[60] 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).
[61] 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. · Zbl 1152.68572
[62] Pesant, G., & Gendreau, M. (1999). A constraint programming framework for local search methods. Journal of Heuristics, 5(3), 255–279. · Zbl 1064.90577 · doi:10.1023/A:1009694016861
[63] 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). · Zbl 1142.90503
[64] 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. · Zbl 1044.68792
[65] 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).
[66] 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.
[67] Regin, J. C. (2004). Global constraints and filtering algorithms. In M. Milano (Ed.), Constraint and integer programming. Dordrecht: Kluwer Academic Publisher.
[68] 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.
[69] 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. · doi:10.1002/spe.4380230507
[70] 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. · Zbl 05459334 · doi:10.1145/1065887.1065889
[71] 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.
[72] Tarim, A., Manandhar, S., & Walsh, T. (2006). Stochastic constraint programming: a scenario-based approach. Constraints, 11, 53–80. · Zbl 1103.68828 · doi:10.1007/s10601-006-6849-7
[73] Van Hentenryck, P. (1999). The OPL optimization programming language. Cambridge: MIT Press.
[74] Van Hentenryck, P., & Michel, L. (2005). Constraint-based local search. Cambridge: MIT Press. · Zbl 1153.90582
[75] van Hoeve, W. J. (2006). The alldifferent constraint: a systematic overview. URL www.cs.cornell.edu/\(\sim\)vanhoeve/papers/alldiff.pdf .
[76] Walsh, T. (2002). Stochastic constraint programming. In F. van Harmelen (Ed.), Proc. of the European conference on artificial intelligence, ECAI. Amsterdam: IOS Press.
[77] Zhou, N. F. (2005). Finite-domain constraint propagators in action rules. Theory and Practice of Logic Programming (4–5).
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.