Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Auto-tabling for subproblem presolving in MiniZinc
Uppsala University, Sweden.
Uppsala University, Sweden.
RISE - Research Institutes of Sweden, ICT, SICS. (Computer Systems Laboratory,)ORCID iD: 0000-0003-3079-8095
Uppsala University, Sweden.
Show others and affiliations
2017 (English)In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 22, no 4, p. 512-529Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2017. Vol. 22, no 4, p. 512-529
Keyword [en]
MiniZinc, Modelling methodology, Presolving, Tabling, Artificial intelligence, Constraint model, Original model, Solving performance, Constraint theory
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:ri:diva-32426DOI: 10.1007/s10601-017-9270-5Scopus ID: 2-s2.0-85020249248OAI: oai:DiVA.org:ri-32426DiVA, id: diva2:1153814
Funder
Swedish Research Council
Note

Funding details: Uppsala Universitet; Funding details: 2015-4910, VR, Vetenskapsrådet

Available from: 2017-10-31 Created: 2017-10-31 Last updated: 2018-01-18Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Carlsson, Mats
By organisation
SICS
In the same journal
Constraints
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 6 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
v. 2.33.0