×

Explaining the cumulative propagator. (English) Zbl 1226.68099

Summary: The global cumulative constraint was proposed for modelling cumulative resources in scheduling problems for finite domain (FD) propagation. Since that time a great deal of research has investigated new stronger and faster filtering techniques for cumulative, but still most of these techniques only pay off in limited cases or are not scalable. Recently, the “lazy clause generation” hybrid solving approach has been devised which allows a finite domain propagation engine possible to take advantage of advanced SAT technology, by “lazily” creating a SAT model of an FD problem as computation progresses. This allows the solver to make use of SAT explanation and autonomous search capabilities. In this article we show how, once we use lazy clause generation, modelling the cumulative constraint by decomposition creates a highly competitive version of cumulative. Using decomposition into component parts automatically makes the propagator incremental and able to explain itself. We then show how, using the insights from the behaviour of the decomposition, we can create global cumulative constraints that explain their propagation. We compare these approaches to explaining the cumulative constraint on resource constrained project scheduling problems. All our methods are able to close a substantial number of open problems from the well-established PSPlib benchmark library of resource-constrained project scheduling problems.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aggoun, A., & Beldiceanu, N. (1993). Extending CHIP in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling, 17(7), 57–73. · Zbl 00269355
[2] Baptiste, P., & Le Pape, C. (2000). Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems. Constraints, 5(1–2), 119–139. · Zbl 0941.90030
[3] Blazewicz, J., Lenstraand, J. K., & Rinnooy Kan, A. H. G. (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5, 11–24. · Zbl 0516.68037
[4] Carlier, J., & Pinson, E. (2004). Jackson’s pseudo-preemptive schedule and cumulative scheduling problems. Discrete Applied Mathematics, 145(1), 80–94. doi: 10.1016/j.dam.2003.09.009 . · Zbl 1058.90023
[5] Caseau, Y., & Laburthe, F. (1996). Cumulative scheduling with task intervals. In Procs. of the 1996 Joint International Conference and Symposium on Logic Programming (pp. 363–377). MIT. citeseer.ist.psu.edu/caseau94cumulative.html .
[6] Claessen, K., Een, N., Sheeran, M., Sörensson, N., Voronov, A., & Åkesson, K. (2009). Sat-solving in practice, with a tutorial example from supervisory control. Discrete Event Dynamic Systems, 19(4), 495–524. doi: 10.1007/s10626-009-0081-8 . · Zbl 1180.93065
[7] Davis, M., Logemman, G., & Loveland, D. (1962). A machine program for theorem proving. Communications of the ACM, 5(7), 394–397. · Zbl 0217.54002
[8] Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49, 61–95. · Zbl 0737.68070
[9] Demeulemeester, E. L., & Herroelen, W. S. (1997). New benchmark results for the resource-constrained project scheduling problem. Management Science, 43(11), 1485–1492. · Zbl 0914.90160
[10] Eén, N., & Sörensson, N. (2003). An extensible SAT-solver. In E. Giunchiglia & A. Tacchella (Eds.), Proceedings of SAT 2003, LNCS (Vol. 2919, pp. 502–518). Heidelberg: Springer. · Zbl 1204.68191
[11] El-Kholy, A. O. (1996). Resource feasibility in planning. Ph.D. thesis, Imperial College, University of London.
[12] Erschler, J., & Lopez, P. (1990). Energy-based approach for task scheduling under time and resources constraints. In 2nd International Workshop on Project Management and Scheduling (pp. 115–121). France: Compiègne.
[13] Feydy, T., & Stuckey, P. J. (2009). Lazy clause generation reengineered. In I. Gent (Ed.), Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming, LNCS (Vol. 5732, pp. 352–366). Springer-Verlag. doi: 10.1007/978-3-642-04244-7_29 .
[14] Hartmann, S., & Kolisch, R. (2000). Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. European Journal of Operational Research, 127(2), 394–407. doi: 10.1016/S0377-2217(99)00485-3 . · Zbl 0985.90036
[15] Jussien, N. (2003). The versatility of using explanations within constraint programming. Research Report 03-04-INFO, École des Mines de Nantes, Nantes, France. http://www.emn.fr/jussien/publications/jussien-RR0304.pdf .
[16] Jussien, N., & Barichard, V. (2000). The PaLM system: Explanation-based constraint programming. In Proceedings of Techniques foR Implementing Constraint Programming Systems (TRICS 2000) (pp. 118–133). http://www.emn.fr/jussien/publications/jussien-WCP00.pdf .
[17] Jussien, N., & Lhomme, O. (2002). Local search with constraint propagation and conflict-based heuristics. Artificial Intelligence, 139(1), 21–45. · Zbl 1015.68056
[18] Jussien, N., Debruyne, R., & Boizumault, P. (2000). Maintaining arc-consistency within dynamic backtracking. In Principles and Practice of Constraint Programming–CP 2000, no. 1894 in Lecture Notes in Computer Science (pp. 249–261). Singapore: Springer-Verlag. · Zbl 1044.68772
[19] Katsirelos, G., & Bacchus, F. (2005). Generalized nogoods in csps. In M. M. Veloso & S. Kambhampati (Eds.), National Conference on Artificial Intelligence (pp. 390–396). AAAI Press/The MIT.
[20] Kolisch, R. (1996). Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90(2), 320–333. doi: 10.1016/0377-2217(95)00357-6 . · Zbl 0916.90151
[21] Kolisch, R., & Hartmann, S. (2006). Experimental investigation of heuristics for resource-constrained project scheduling: An update. European Journal of Operational Research, 174(1), 23–37. doi: 10.1016/j.ejor.2005.01.065 . · Zbl 1116.90047
[22] Kolisch, R., & Sprecher, A. (1997). PSPLIB–A project scheduling problem library. European Journal of Operational Research, 96(1), 205–216. doi: 10.1016/S0377-2217(96)00170-1 . · Zbl 0947.90587
[23] Laborie, P. (2005). Complete MCS-based search: Application to resource constrained project scheduling. In L. P. Kaelbling & A. Saffiotti (Eds.), Proceedings IJCAI 2005 (pp. 181–186). Professional Book Center. http://ijcai.org/papers/0571.pdf .
[24] Lahrichi, A. (1982). Scheduling: The notions of hump, compulsory parts and their use in cumulative problems. Comptes Rendus de l’Académie des Sciences. Paris, Série 1, Mathématique, 294(2), 209–211. · Zbl 0496.68023
[25] Liess, O., & Michelon, P. (2008). A constraint programming approach for the resource-constrained project scheduling problem. Annals of Operations Research, 157(1), 25–36. doi: 10.1007/s10479-007-0188-y . · Zbl 1151.90444
[26] Marriott, K., Nethercote, N., Rafeh, R., Stuckey, P. J., Garcia de la Banda, M., & Wallace, M. G. (2008). The design of the Zinc modelling language. Constraints, 13(3), 229–267. doi: 10.1007/s10601-008-9041-4 . · Zbl 1146.68352
[27] Mercier, L., & Van Hentenryck, P. (2008). Edge finding for cumulative scheduling. INFORMS Journal on Computing, 20(1), 143–153. doi: 10.1287/ijoc.1070.0226 . · Zbl 1243.90068
[28] Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., & Malik, S. (2001). Chaff: Engineering an efficient SAT solver. In Design automation conference (pp. 530–535). New York: ACM. doi: 10.1145/378239.379017 .
[29] Nuijten, W. P. M. (1994). Time and resource constrained scheduling. Ph.D. thesis, Eindhoven University of Technology. · Zbl 0837.90068
[30] Ohrimenko, O., Stuckey, P., & Codish, M. (2009). Propagation via lazy clause generation. Constraints, 14(3), 357–391. · Zbl 1192.68654
[31] Ohrimenko, O., Stuckey, P. J., & Codish, M. (2007). Propagation = lazy clause generation. In Procs. of the CP2007, LNCS (Vol. 4741, pp. 544–558). Springer-Verlag. doi: 10.1007/978-3-540-74970-7_39 . · Zbl 1145.68527
[32] PSPLib–project scheduling problem library (2009). http://129.187.106.231/psplib/ . Accessed 23 April 2009.
[33] Schulte, C., & Stuckey, P. (2008). Efficient constraint propagation engines. ACM Transactions on Programming Languages and Systems, 31(1), 1–43. · Zbl 05517454
[34] Schutt, A. (2006). Entwicklung suchraumeinschränkender Verfahren zur Constraint-basierten Lösung kumulativer Ressourcenplanungsprobleme. Master’s thesis, Humboldt-Universität zu Berlin.
[35] Schutt, A., Feydy, T., Stuckey, P. J., & Wallace, M. G. (2009). Why cumulative decomposition is not as bad as it sounds. In I. Gent (Ed.), Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming, LNCS (Vol. 5732, pp. 746–761). Springer-Verlag.
[36] Schutt, A., Wolf, A., & Schrader, G. (2006). Not-first and not-last detection for cumulative scheduling in ${\(\backslash\)cal O}(n\^3\(\backslash\)log n)$ . In Declarative programming for knowledge management, Lecture Notes in Computer Science (Vol. 4369, pp. 66–80). Springer-Verlag. doi: 10.1007/11963578 . INAP 2005–16th international conference on applications of declarative programming and knowledge management.
[37] Vilím, P. (2005). Computing explanations for the unary resource constraint. In Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization problems, LNCS (Vol. 3524, pp. 396–409). Springer-Verlag. doi: 10.1007/11493853_29 . http://kti.ms.mff.cuni.cz/\(\sim\)vilim/cpaior2005.pdf . · Zbl 1133.68439
[38] Vilím, P. (2009). Edge finding filtering algorithm for discrete cumulative resources in ${\(\backslash\)mathcal O}(kn\(\backslash\)log n)$ . In Principles and Practice of Constraint Programming–CP 2009, LNCS (Vol. 5732, pp. 802–816). Springer-Verlag. doi: 10.1007/978-3-642-04244-7_62 .
[39] Wolf, A., & Schrader, G. (2006). ${\(\backslash\)mathcal O}(n\(\backslash\)log n)$ overload checking for the cumulative constraint and its application. In Declarative programming for knowledge management, Lecture Notes in Computer Science (Vol. 4369, pp. 88–101). Springer-Verlag. doi: 10.1007/11963578_8 . INAP 2005–16th international conference on applications of declarative programming and knowledge management.
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.