×

How efficient is a global constraint in practice? A fair experimental framework. (English) Zbl 1394.90431

Summary: Propagation is at the very core of \(t\) can provide signi: 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. While experimental evaluation is here of the greatest importance, there exists no systematic and flexible methodology to measure the exact benefits provided by a given (new) filtering procedure. This work proposes such a framework by relying on replaying search trees to obtain more realistic assessments. Reducing propagation overhead is done chiefly by 1) devising more efficient algorithms or by 2) using on-line control policies to limit the propagator activations, i.e., mechanisms to reduce the number of propagator calls. 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. In order to visualize benefits of actual global constraints and the potential of their improvement, we suggest the use of performance profiles. Our approach is showcased for well-known global constraints: alldifferent, cumulative, binpacking and unary (with transition times).

MSC:

90C10 Integer programming
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. · doi:10.1016/0895-7177(93)90068-A
[2] Ait-Kaci, H., & Des Flambertins, F. (1999). Warren’s abstract machine—a tutorial reconstruction (pp. 114). Cambridge: MIT Press Cambridge. · Zbl 1204.68188
[3] 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 · doi:10.1023/A:1009822502231
[4] Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-based scheduling: applying constraint programming to scheduling problems. In International Series in Operations Research & Management Science (Vol. 39). Springer, Berlin. · Zbl 1094.90002
[5] Beldiceanu, N., & Contejean, E. (1994). Introducing global constraints in CHIP. Mathematical and Computer Modelling, 20(12), 97-123. · Zbl 0816.68048 · doi:10.1016/0895-7177(94)90127-9
[6] Benhamou, F. (1996). Heterogeneous constraint solving. In International conference on algebraic and logic programming (pp. 62-76). Springer, Berlin. · Zbl 1355.68030
[7] Bergman, D., Ciré, A.A., & van Hoeve, W.J. (2014). MDD propagation for sequence constraints. Journal of Artificial Intelligence Research (JAIR), 50, 697-722. · Zbl 1366.68072
[8] Bergman, D., Cire, A.A., van Hoeve, W.J., & Hooker, J. (2016). Decision diagrams for optimization. Springer International Publishing. · Zbl 06653190
[9] Berthold, T., Heinz, S., & Schulz, J. (2011). An approximative criterion for the potential of energetic reasoning. In Theory and practice of algorithms in (computer) systems (pp. 229-239). · Zbl 1325.90035
[10] Bessière, C., & Debruyne, R. (2005). Optimal and suboptimal singleton arc consistency algorithms. In International joint conference on artificial intelligence (pp. 54-59). · Zbl 1210.68103
[11] Bessiere, C., & Régin, J.C. (1997). Arc consistency for general constraint networks: preliminary results. In International joint conference on artificial intelligence (pp. 398-404). Citeseer.
[12] Bessiere, C., & Van Hentenryck, P. (2003). To be or not to be... a global constraint. In International conference on principles and practice of constraint programming (pp. 789-794). Springer, Berlin. · Zbl 1273.68334
[13] Brand, S., Narodytska, N., Quimper, C., Stuckey, P.J., & Walsh, T. (2007). Encodings of the sequence constraint. In International conference on principles and practice of constraint programming (pp. 210-224). · Zbl 1145.68507
[14] Cheng, K.C.K., & Yap, R.H.C. (2010). An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints. Constraints, 15(2), 265-304. · Zbl 1204.68188 · doi:10.1007/s10601-009-9087-y
[15] Dejemeppe, C., Van Cauwelaert, S., & Schaus, P. (2015). The unary resource with transition times. In International conference on principles and practice of constraint programming (pp. 89-104). Springer, Berlin. · Zbl 1446.90085
[16] Deransart, P., Hermenegildo, M.V., & Maluszynski, J. (2000). Analysis and visualization tools for constraint programming: constraint debugging. In Lecture Notes in Computer Science (Vol. 1870). Springer, Berlin. · Zbl 0816.68048
[17] Derrien, A., & Petit, T. (2014). A new characterization of relevant intervals for energetic reasoning. In International conference on principles and practice of constraint programming (pp. 289-297). Springer, Berlin. · Zbl 1204.68188
[18] Dincbas, M., Simonis, H., & Van Hentenryck, P. (1990). Solving large combinatorial problems in logic programming. The Journal of Logic Programming, 8 (1), 75-93. · Zbl 0719.68013 · doi:10.1016/0743-1066(90)90052-7
[19] Dolan, E.D., & Moré, J.J. (2002). Benchmarking optimization software with performance profiles. Mathematical Programming, 91(2), 201-213. · Zbl 1049.90004 · doi:10.1007/s101070100263
[20] Du Boisberranger, J., Gardy, D., Lorca, X., & Truchet, C. (2013). When is it worthwhile to propagate a constraint? A probabilistic analysis of alldifferent. In Workshop on analytic algorithmics and combinatorics (pp. 80-90). SIAM. · Zbl 1430.68290
[21] Ducomman, S., Cambazard, H., & Penz, B. (2016). Alternative filtering for the weighted circuit constraint: Comparing lower bounds for the tsp and solving tsptw. In AAAI conference on artificial intelligence. · Zbl 1366.68072
[22] Erschler, J., & Lopez, P. (1990). Energy-based approach for task scheduling under time and resources constraints. In International workshop on project management and scheduling (pp. 115-121).
[23] Focacci, F., Lodi, A., Milano, M., & Vigo, D. (1999). Solving TSP through the integration of OR and CP techniques. Electronic Notes in Discrete Mathematics, 1, 13-25. · Zbl 0990.90553 · doi:10.1016/S1571-0653(04)00002-2
[24] Gay, S., Hartert, R., Lecoutre, C., & Schaus, P. (2015). Conflict ordering search for scheduling problems. In International conference on principles and practice of constraint programming (pp. 140-148). Springer.
[25] Gay, S., Hartert, R., & Schaus, P. (2015). Simple and scalable time-table filtering for the cumulative constraint. In International conference on principles and practice of constraint programming (pp. 149-157). Springer, Berlin. · Zbl 1459.90093
[26] Gay, S., Hartert, R., & Schaus, P. (2015). Time-table disjunctive reasoning for the cumulative constraint. In International conference on integration of artificial intelligence (AI) and operations research (OR) techniques in constraint programming (pp. 157-172). Springer, Berlin. · Zbl 1459.90093
[27] Harvey, W.D., & Ginsberg, M.L. (1995). Limited discrepancy search. In International joint conference on artificial intelligence (pp. 607-615). · Zbl 0941.90030
[28] van Hoeve, W.J., Pesant, G., Rousseau, L., & Sabharwal, A. (2006). Revisiting the sequence constraint. In International conference on principles and practice of constraint programming (pp. 620-634). · Zbl 1160.68573
[29] Jefferson, C., Moore, N.C., Nightingale, P., & Petrie, K.E. (2010). Implementing logical connectives in constraint programming. Artificial Intelligence, 174(16-17), 1407-1429. · Zbl 1210.68103 · doi:10.1016/j.artint.2010.07.001
[30] Kolisch, R., Schwindt, C., & Sprecher, A. (1999). Benchmark instances for project scheduling problems. In Project scheduling (pp. 197-212). Springer, Berlin.
[31] Langevine, L., Deransart, P., & Ducassé, M. (2003). A generic trace schema for the portability of CP(FD) debugging tools. In International workshop on constraint solving and constraint logic programming (pp. 171-195). Springer, Berlin.
[32] Le Pape, C., Couronné, P., Vergamini, D., & Gosselin, V. (1994). Time-versus-capacity compromises in project scheduling. In Workshop of the UK planning and scheduling. Citeseer. · Zbl 1334.90170
[33] Letort, A., Beldiceanu, N., & Carlsson, M. (2012). A scalable sweep algorithm for the cumulative constraint. In International conference on principles and practice of constraint programming (pp. 439-454). Springer, Berlin. · Zbl 1382.68225
[34] López-Ortiz, A., Quimper, C.G., Tromp, J., & Van Beek, P. (2003). A fast and simple algorithm for bounds consistency of the alldifferent constraint. In International joint conference on artificial intelligence (Vol. 3, pp. 245-250).
[35] McCreesh, C., & Prosser, P. (2015). A parallel, backjumping subgraph isomorphism algorithm using supplemental graphs. In International conference on principles and practice of constraint programming (pp. 295-312). Springer, Berlin.
[36] Müller, T., & Würtz, J. (1995). Constructive disjunction in oz. In Workshop Logische Programmierung. Citeseer.
[37] OscaR Team: OscaR: Scala in OR (2012). Available from https://bitbucket.org/oscarlib/oscar.
[38] Pelsser, F., Schaus, P., & Régin, J.C. (2013). Revisiting the cardinality reasoning for binpacking constraint. In International conference on principles and practice of constraint programming (pp. 578-586). Springer, Berlin.
[39] Pisinger, D., & Ropke, S. (2010). Large neighborhood search. In Handbook of metaheuristics (pp. 399-419). Springer, Berlin.
[40] Régin, J.C. (1994). A filtering algorithm for constraints of difference in CSPs. In AAAI conference on artificial intelligence (Vol. 94, pp. 362-367). · Zbl 0775.90293
[41] Reinelt, G. (1991). Tsplib—a traveling salesman problem library. ORSA Journal on Computing, 3(4), 376-384. · Zbl 0775.90293 · doi:10.1287/ijoc.3.4.376
[42] Schaus, P. (2009). Solving balancing and bin-packing problems with constraint programming. Ph.D. thesis, Université catholique de Louvain, Louvain-la-Neuve. · Zbl 0775.90293
[43] Schulte, C. (1997). Oz explorer: a visual constraint programming tool. In L. Naish (Ed.), Proceedings of the fourteenth international conference on logic programming (pp. 286-300). Leuven: The MIT Press.
[44] Schulte, C. (1999). Comparing trailing and copying for constraint programming. In International conference on logic programming (Vol. 99, pp. 275-289).
[45] 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. · doi:10.1145/1065887.1065889
[46] Schulte, C., & Tack, G. (2009). Weakly monotonic propagators. In International conference on principles and practice of constraint programming (pp. 723-730). Springer, Berlin.
[47] Shaw, P. (2004). A constraint for bin packing. In International conference on principles and practice of constraint programming (pp. 648-662). Springer, Berlin. · Zbl 1152.68586
[48] Shishmarev, M., Mears, C., Tack, G, & de la Banda, M.G. (2015). Visual search tree profiling. In International conference on principles and practice of constraint programming. Springer, Berlin. · Zbl 1334.90170
[49] Shishmarev, M., Mears, C., Tack, G, & de la Banda, M.G. (2016). Learning from learning solvers. In International conference on principles and practice of constraint programming (pp. 455-472). Springer, Berlin.
[50] Shishmarev, M., Mears, C., Tack, G, & de la Banda, M.G. (2016). Visual search tree profiling. Constraints, 21(1), 77-94. · Zbl 1334.90170 · doi:10.1007/s10601-015-9202-1
[51] Simonis, H., Davern, P., Feldman, J., Mehta, D., Quesada, L., & Carlsson, M. (2010). A generic visualization platform for CP. In International conference on principles and practice of constraint programming (pp. 460-474). Springer, Berlin.
[52] Smith, B.M. (2005). Modelling for constraint programming. In Lecture notes for the first international summer school on constraint programming.
[53] Tack, G. (2009). Constraint propagation—models, techniques, implementation. Ph.D. thesis, Saarland University, Germany.
[54] Van Beek, P. (2006). Backtracking search algorithms. In Handbook of constraint programming (pp. 85-134).
[55] Van Cauwelaert, S., Lombardi, M., & Pierre, S. (2014). Supervised learning to control energetic reasoning: feasibility study. In Proceedings of the doctoral program of CP2014.
[56] Van Cauwelaert, S., Lombardi, M., & Schaus, P. (2015). Understanding the potential of propagators. In International conference on integration of artificial intelligence (AI) and operations research (OR) techniques in constraint programming (pp. 427-436). Springer, Berlin. · Zbl 1459.68195
[57] Van Cauwelaert, S., Lombardi, M., & Schaus, P. (2016). A visual web tool to perform what-if analysis of optimization approaches. Tech. rep., UCLouvain.
[58] Van Hentenryck, P., & Dincbas, M. (1987). Forward checking in logic programming. In International conference on logic programming (pp. 229-256). · Zbl 0623.68006
[59] Vilım, P. (2007). Global constraints in scheduling. Ph.D. thesis, Charles University in Prague, Faculty of Mathematics and Physics, Department of Theoretical Computer Science and Mathematical Logic, KTIML MFF, Universita Karlova, Praha 1.
[60] Warren, D. (1983). An abstract Prolog instruction set (Vol. 309). Menlo Park: SRI International.
[61] Würtz, J., & Müller, T. (1996). Constructive disjunction revisited. In Görz, G., & Hölldobler, S. (Eds.) KI-96: Advances in artificial intelligence. KI 1996. Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence), (Vol. 1137, pp. 377386). Berlin: Springer.
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.