nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Automatic Discovery and Exploitation of Promising Subproblems for Tabulation

verfasst von : Özgür Akgün, Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale, András Z. Salamon

Erschienen in: Principles and Practice of Constraint Programming

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The performance of a constraint model can often be improved by converting a subproblem into a single table constraint. In this paper we study heuristics for identifying promising subproblems. We propose a small set of heuristics to identify common cases such as expressions that will propagate weakly. The process of discovering promising subproblems and tabulating them is entirely automated in the tool Savile Row. A cache is implemented to avoid tabulating equivalent subproblems many times. We give a simple algorithm to generate table constraints directly from a constraint expression in Savile Row. We demonstrate good performance on the benchmark problems used in earlier work on tabulation, and also for several new problem classes.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Correction to: MLIC: A MaxSAT-Based Framework for Learning Interpretable Classification Rules

Nächstes Kapitel Propagating Regular Membership with Dashed Strings

Mohr, R., Masini, G.: Good old discrete relaxation. In: Proceedings of ECAI 1988, pp. 651–656. Pitman Publishing (1988)

Gent, I.P., Jefferson, C., Miguel, I., Nightingale, P.: Data structures for generalised arc consistency for extensional constraints. In: Proceedings of AAAI 2007, pp. 191–197. AAAI Press (2007). http://www.aaai.org/Papers/AAAI/2007/AAAI07-029.pdf

Lecoutre, C.: STR2: optimized simple tabular reduction for table constraints. Constraints 16(4), 341–371 (2011). https://doi.org/10.1007/s10601-011-9107-6MathSciNetCrossRefMATH

Bessiere, C.: Constraint propagation. In: Handbook of Constraint Programming, pp. 29–83. Elsevier (2006)

Gent, I.P., Jefferson, C., Kelsey, T., Lynce, I., Miguel, I., Nightingale, P., Smith, B.M., Tarim, S.A.: Search in the patience game ‘Black Hole’. AI Communications 20(3), 211–226 (2007). https://content.iospress.com/articles/ai-communications/aic405MathSciNetMATH

Gargani, A., Refalo, P.: An efficient model and strategy for the steel mill slab design problem. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 77–89. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74970-7_8CrossRef

Dekker, J.J., Björdal, G., Carlsson, M., Flener, P., Monette, J.N.: Auto-tabling for subproblem presolving in MiniZinc. Constraints 22(4), 512–529 (2017). https://doi.org/10.1007/s10601-017-9270-5MathSciNetCrossRefMATH

Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: towards a standard cp modelling language. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74970-7_38CrossRef

IBM Knowledge Center: The strong constraint (2017). https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.ide.help/OPL_Studio/opllang_quickref/topics/tlr_oplsch_strong.html

10.

Le Provost, T., Wallace, M.: Domain independent propagation. In: Proceedings of FGCS: International Conference on Fifth Generation Computer Systems, pp. 1004–1011. IOS Press (1992). http://www.webmail.eclipseclp.org/reports/corefgcs.pdf

11.

Nightingale, P., Akgün, Ö., Gent, I.P., Jefferson, C., Miguel, I.: Automatically improving constraint models in Savile Row through associative-commutative common subexpression elimination. In: O’Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 590–605. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10428-7_43CrossRef

12.

Nightingale, P., Spracklen, P., Miguel, I.: Automatically improving SAT encoding of constraint problems through common subexpression elimination in savile row. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 330–340. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23219-5_23CrossRef

13.

Nightingale, P., Akgün, O., Gent, I.P., Jefferson, C., Miguel, I., Spracklen, P.: Automatically improving constraint models in Savile Row. Artif. Intell. 251, 35–61 (2017). https://doi.org/10.1016/j.artint.2017.07.001MathSciNetCrossRefMATH

14.

Nightingale, P., Rendl, A.: Essence’ description (2016). arXiv:1601.02865 [cs.AI]

15.

Bessière, C., Hebrard, E., Hnich, B., Walsh, T.: The complexity of reasoning with global constraints. Constraints 12(2), 239–259 (2007). https://doi.org/10.1007/s10601-006-9007-3MathSciNetCrossRefMATH

16.

Régin, J.C.: Generalized arc consistency for global cardinality constraint. In: Proceedings of AAAI 1996, pp. 209–215. AAAI Press (1996). http://www.aaai.org/Papers/AAAI/1996/AAAI96-031.pdf

17.

Gent, I.P., Jefferson, C., Miguel, I.: Minion: A fast scalable constraint solver. In: Proceedings of ECAI 2006, pp. 98–102. IOS Press (2006). http://ebooks.iospress.nl/volumearticle/2658

18.

Lecoutre, C., Sais, L., Tabary, S., Vidal, V.: Last conflict based reasoning. In: Proceedings of ECAI 2006, pp. 133–137. IOS Press (2006). http://ebooks.iospress.nl/volumearticle/2665

19.

Chu, G., Stuckey, P.J., Schutt, A., Ehlers, T., Gange, G., Francis, K.: Chuffed (2018). https://github.com/chuffed/chuffed/

20.

Akgün, Ö., Gent, I.P., Jefferson, C., Miguel, I., Nightingale, P., Salamon, A.Z.: Tabulation experimental software and additional results (2018). https://doi.org/10.5281/zenodo.1290656, https://github.com/stacs-cp/cp2018-tabulation

21.

Van Hentenryck, P., Michel, L., Perron, L., Régin, J.-C.: Constraint programming in OPL. In: Nadathur, G. (ed.) PPDP 1999. LNCS, vol. 1702, pp. 98–116. Springer, Heidelberg (1999). https://doi.org/10.1007/10704567_6CrossRef

22.

CSPLib: A problem library for constraints (1999). http://www.csplib.org

23.

Erdos, P., Sárközy, A.: On sets of coprime integers in intervals. Hardy-Ramanujan J. 16, 1–20 (1993). https://hal.archives-ouvertes.fr/hal-01108688

Titel: Automatic Discovery and Exploitation of Promising Subproblems for Tabulation
verfasst von: Özgür Akgün
Ian P. Gent
Christopher Jefferson
Ian Miguel
Peter Nightingale
András Z. Salamon
Verlag: Springer International Publishing
Buch: Principles and Practice of Constraint Programming
Print ISBN: 978-3-319-98333-2

Electronic ISBN: 978-3-319-98334-9

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-98334-9_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner