×

Auto-tabling for subproblem presolving in MiniZinc. (English) Zbl 1425.68386

Summary: A well-known and powerful constraint model reformulation is to compute the solutions to a model part, say a custom constraint predicate, and tabulate them within an extensional constraint that replaces that model part. Despite the possibility of achieving higher solving performance, this tabling reformulation is often not tried, because it is tedious to perform; further, if successful, it obfuscates the original model. In order to encourage modellers to try tabling, we extend the MiniZinc toolchain to perform the automatic tabling of suitably annotated predicate definitions, without requiring any changes to solvers, thereby eliminating both the tedium and the obfuscation. Our experiments show that automated tabling yields the same tables as manual tabling, and that tabling is beneficial for solvers of several solving technologies.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdennadher, S., & Rigotti, C. (2004). Automatic generation of rule-based constraint solvers over finite domains. ACM Transactions on Computational Logic, 5(2), 177-205. · Zbl 1367.68259 · doi:10.1145/976706.976707
[2] Belov, G., Stuckey, P.J., Tack, G., & Wallace, M. (2016). Improved linearization of constraint programming models. In Rueher, M. (Ed.), CP 2016, LNCS, (Vol. 9892 pp. 49-65): Springer.
[3] Bergman, D., Cire, A.A., van Hoeve, W.J., & Hooker, J. (2016). Decision diagrams for optimization. Springer. · Zbl 06653190
[4] Bessière, C., & Régin, J.C. (1999). Enforcing arc consistency on global constraints by solving subproblems on the fly. In Jaffar, J. (Ed.), CP 1999, LNCS, (Vol. 1713 pp. 103-117): Springer. · Zbl 0961.68124
[5] Björdal, G., Monette, J.N., Flener, P., & Pearson, J. (2015). A constraint-based local search backend for MiniZinc. Constraints, 20(3), 325-345. · Zbl 1325.90076 · doi:10.1007/s10601-015-9184-z
[6] Bofill, M., Suy, J., & Villaret, M. (2010). A system for solving constraint satisfaction problems with SMT. In Strichman, O., & Szeider, S. (Eds.), SAT 2010, LNCS, (Vol. 6175 pp. 300-305): Springer. · Zbl 1306.68153
[7] Carlsson, M., Johansson, M., & Larson, J. (2017). Scheduling double round-robin tournaments with divisional play using constraint programming. European Journal of Operational Research, 259(3), 1180-1190. · Zbl 1402.90047 · doi:10.1016/j.ejor.2016.11.033
[8] Carlsson, M., Ottosson, G., & Carlson, B. (1997). An open-ended finite domain constraint solver. In Glaser, H., Hartel, P., & Kuchen, H. (Eds.), PLILP 1997, LNCS, (Vol. 1292 pp. 191-206): Springer. · Zbl 1405.68326
[9] Cheng, K.C.K., & Yap, R.H.C. (2008). Maintaining generalized arc consistency on ad hoc r-ary constraints. In Stuckey, P.J. (Ed.), CP 2008, LNCS, (Vol. 5202 pp. 509-523): Springer.
[10] Chu, G. (2011). Improving combinatorial optimization. Ph.D. thesis, Department of Computing and Information Systems. Australia: University of Melbourne.
[11] De Cat, B., Bogaerts, B., Devriendt, J., & Denecker, M. (2013). Model expansion in the presence of function symbols using constraint programming. In Brodsky, A. (Ed.), ICTAI 2013 (pp. 1068-1075): IEEE. The MinisatID solver is available from https://dtai.cs.kuleuven.be/software/minisatid. · Zbl 1367.68259
[12] De Landtsheer, R., & Ponsard, C. (2013). OscaR.cbls: An open source framework for constraint-based local search, ORBEL-27, the 27th annual conference of the Belgian Operational Research Society. Available at http://www.orbel.be/orbel27/pdf/abstract293.pdf; the OscaR.cbls solver is available from https://bitbucket.org/oscarlib/oscar/branch/CBLS. · Zbl 1402.90047
[13] Dekker, J.J. (2016). Sub-problem pre-solving in MiniZinc. Master’s thesis, Department of Information Technology, Uppsala University, Sweden. Available at http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-307145.
[14] Demeulenaere, J., Hartert, R., Lecoutre, C., Perez, G., Perron, L., Régin, J., & Schaus, P. (2016). Compact-table: Efficiently filtering table constraints with reversible sparse bit-sets. In Rueher, M. (Ed.), CP 2016, LNCS, (Vol. 9892 pp. 207-223): Springer. · Zbl 1151.90525
[15] Eén, N., & Biere, A. (2005). Effective preprocessing in SAT through variable and clause elimination. In Bacchus, F., & Walsh, T. (Eds.), SAT 2005, LNCS, (Vol. 3569 pp. 61-75): Springer. · Zbl 1128.68463
[16] Gecode Team (2016). Gecode: A generic constraint development environment. http://www.gecode.org.
[17] Gent, I.P., Jefferson, C., Kelsey, T., Lynce, I., Miguel, I., Nightingale, P., Smith, B.M., & Tarim, S.A. (2007). Search in the patience game ’black hole’. AI Communications, 20(3), 211-226. · Zbl 1151.90525
[18] Gent, I.P., Jefferson, C., Linton, S., Miguel, I., & Nightingale, P. (2014). Generating custom propagators for arbitrary constraints. Artificial Intelligence, 211, 1-33. · Zbl 1405.68326 · doi:10.1016/j.artint.2014.03.001
[19] Google Optimization Team (2016). or-tools: Google’s software suite for combinatorial optimization. https://developers.google.com/optimization.
[20] IBM Knowledge Center. The strong constraint. http://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.3/ilog.odms.ide.help/OPL_Studio/opllang_quickref/topics/tlr_oplsch_strong.html. · Zbl 1325.90076
[21] Larson, J., & Johansson, M. (2014). Constructing schedules for sports leagues with divisional and round-robin tournaments. Journal of Quantitative Analysis in Sports, 10 (2), 119-129. · doi:10.1515/jqas-2013-0090
[22] Larson, J., Johansson, M., & Carlsson, M. (2014). An integrated constraint programming approach to scheduling sports leagues with divisional and round-robin tournaments. In Simonis, H. (Ed.), CPAIOR 2014, LNCS, (Vol. 8451 pp. 144-158): Springer. · Zbl 06298789
[23] Le Provost, T., & Wallace, M. (1992). Domain independent propagation, FGCS 1992, International conference on fifth generation computer systems (pp. 1004-1011): IOS Press. · Zbl 0862.68023
[24] Leo, K., & Tack, G. (2015). Multi-pass high-level presolving. In Yang, Q., & Wooldridge, M. (Eds.), IJCAI 2015 (pp. 346-352): AAAI Press.
[25] Monette, J.N., Flener, P., & Pearson, J. (2015). Automated auxiliary variable elimination through on-the-fly propagator generation. In Pesant, G. (Ed.), CP 2015, LNCS, (Vol. 9255 pp. 313-329): Springer.
[26] Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., & Tack, G. (2007). MiniZinc: Towards a standard CP modelling language. In Bessière, C. (Ed.), CP 2007, LNCS. The MiniZinc toolchain is available at http://www.minizinc.org, (Vol. 4741 pp. 529-543): Springer.
[27] Parlett, D. (Ed.) (1990). The Penguin Book of Patience. London: Penguin.
[28] Pesant, G. (2004). A regular language membership constraint for finite sequences of variables. In Wallace, M. (Ed.), CP 2004, LNCS, (Vol. 3258 pp. 482-495): Springer. · Zbl 1152.68573
[29] Rendl, A., Guns, T., Stuckey, P.J., & Tack, G. (2015). MiniSearch: A solver-independent meta-search language for MiniZinc. In Pesant, G. (Ed.), CP 2015, LNCS, (Vol. 9255 pp. 376-392): Springer.
[30] Simonis, H. (2008). Kakuro as a constraint problem. In Flener, P., & Simonis, H. (Eds.), ModRef 2018, the 7th International Workshop on Constraint Modelling and Reformulation. https://www.it.uu.se/research/group/astra/ModRef08/Simonis.pdf.
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.