Abstract
Propagation is at the very core of Constraint Programming (CP): it can provide significant performance boosts as long as the search space reduction is not outweighed by the cost for running the propagators. A lot of research effort in the CP community is directed toward improving this trade-off, which for a given type of filtering amounts to reducing the computation cost. This is done chiefly by 1) devising more efficient algorithms or by 2) using on-line control policies to limit the propagator activations. In both cases, obtaining improvements is a long and demanding process with uncertain outcome. We propose a method to assess the potential gain of both approaches before actually starting the endeavor, providing the community with a tool to best direct the research efforts. Our approach is based on instrumenting the constraint solver to collect statistics, and we rely on replaying search trees to obtain more realistic assessments. The overall approach is easy to setup and is showcased on the Energetic Reasoning (ER) and the Revisited Cardinality Reasoning for BinPacking (RCRB) propagators.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aggoun, A., Beldiceanu, N.: Extending chip in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling 17(7), 57–73 (1993)
Baptiste, P., Le Pape, C.: Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems. Constraints 5(1–2), 119–139 (2000)
Baptiste, P., Le Pape, C., Nuijten, W.: Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems, vol. 39. Springer (2001)
Beldiceanu, N., Carlsson, M.: A new multi-resource \(cumulatives\) constraint with negative heights. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 63–79. Springer, Heidelberg (2002)
Beldiceanu, N., Contejean, E.: Introducing global constraints in chip. Mathematical and computer Modelling 20(12), 97–123 (1994)
Bergman, D., Ciré, A.A., van Hoeve, W.J.: MDD propagation for sequence constraints. J. Artif. Intell. Res. (JAIR) 50, 697–722 (2014)
Berthold, T., Heinz, S., Schulz, J.: An approximative criterion for the potential of energetic reasoning. In: Marchetti-Spaccamela, A., Segal, M. (eds.) TAPAS 2011. LNCS, vol. 6595, pp. 229–239. Springer, Heidelberg (2011)
Bessière, C., Debruyne, R.: Optimal and suboptimal singleton arc consistency algorithms. In: IJCAI-2005, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30-August 5, 2005, pp. 54–59 (2005)
Brand, S., Narodytska, N., Quimper, C.-G., Stuckey, P.J., Walsh, T.: Encodings of the Sequence constraint. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 210–224. Springer, Heidelberg (2007)
Van Cauwelaert, S., Lombardi, M., Schaus, P.: Supervised learning to control energetic reasoning: feasibility study. In: Proceedings of the Doctoral Program CP2014 (2014)
Cheng, K.C.K., Yap, R.H.C.: An mdd-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints. Constraints 15(2), 265–304 (2010)
Derrien, A., Petit, T.: A new characterization of relevant intervals for energetic reasoning. In: O’Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 289–297. Springer, Heidelberg (2014)
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Mathematical programming 91(2), 201–213 (2002)
Erschler, J., Lopez, P.: Energy-based approach for task scheduling under time and resources constraints. In: 2nd international workshop on project management and scheduling, pp. 115–121 (1990)
Kolisch, R., Schwindt, C., Sprecher, A.: Benchmark instances for project scheduling problems. In: Project Scheduling, pp. 197–212. Springer (1999)
Le Pape, C., Couronné, P., Vergamini, D., Gosselin, V.: Time-Versus-Capacity Compromises in Project Scheduling. (1994)
OscaR Team. OscaR: Scala in OR (2012). https://bitbucket.org/oscarlib/oscar
Pelsser, F., Schaus, P., Régin, J.-C.: Revisiting the cardinality reasoning for binpacking constraint. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 578–586. Springer, Heidelberg (2013)
Schaus, P. et al.: Solving balancing and bin-packing problems with constraint programming. PhD thesis, Université catholique de Louvain, Louvain-la-Neuve (2009)
Shaw, P.: A constraint for bin packing. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 648–662. Springer, Heidelberg (2004)
van Hoeve, W.-J., Pesant, G., Rousseau, L.-M., Sabharwal, A.: Revisiting the sequence constraint. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 620–634. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Van Cauwelaert, S., Lombardi, M., Schaus, P. (2015). Understanding the Potential of Propagators. In: Michel, L. (eds) Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015. Lecture Notes in Computer Science(), vol 9075. Springer, Cham. https://doi.org/10.1007/978-3-319-18008-3_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-18008-3_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18007-6
Online ISBN: 978-3-319-18008-3
eBook Packages: Computer ScienceComputer Science (R0)