caa a22 4500 445879254 CHVBK 20180317145537.0 cr unu---uuuuu 170323e20110701xx s 000 0 eng 10.1007/s10601-010-9103-2 doi (NATIONALLICENCE)springer-10.1007/s10601-010-9103-2 Explaining the cumulative propagator [Elektronische Daten] [Andreas Schutt, Thibaut Feydy, Peter Stuckey, Mark Wallace] 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. Springer Science+Business Media, LLC, 2010 Cumulative constraint nationallicence Explanations nationallicence Nogood learning nationallicence Lazy clause generation nationallicence Resource-constrained project scheduling problem nationallicence Schutt Andreas National ICT Australia, Department of Computer Science & Software Engineering, TheUniversityofMelbourne, 3010, Melbourne, Victoria, Australia aut Feydy Thibaut National ICT Australia, Department of Computer Science & Software Engineering, TheUniversityofMelbourne, 3010, Melbourne, Victoria, Australia aut Stuckey Peter National ICT Australia, Department of Computer Science & Software Engineering, TheUniversityofMelbourne, 3010, Melbourne, Victoria, Australia aut Wallace Mark School of Computer Science & Software Engineering, Monash University, 3800, Clayton, Victoria, Australia aut Constraints Springer US; http://www.springer-ny.com 16/3(2011-07-01), 250-282 1383-7133 16:3<250 2011 16 10601 https://doi.org/10.1007/s10601-010-9103-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10601-010-9103-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Schutt Andreas National ICT Australia, Department of Computer Science & Software Engineering, TheUniversityofMelbourne, 3010, Melbourne, Victoria, Australia aut NATIONALLICENCE 700 1- Feydy Thibaut National ICT Australia, Department of Computer Science & Software Engineering, TheUniversityofMelbourne, 3010, Melbourne, Victoria, Australia aut NATIONALLICENCE 700 1- Stuckey Peter National ICT Australia, Department of Computer Science & Software Engineering, TheUniversityofMelbourne, 3010, Melbourne, Victoria, Australia aut NATIONALLICENCE 700 1- Wallace Mark School of Computer Science & Software Engineering, Monash University, 3800, Clayton, Victoria, Australia aut NATIONALLICENCE 773 0- Constraints Springer US; http://www.springer-ny.com 16/3(2011-07-01), 250-282 1383-7133 16:3<250 2011 16 10601 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer