SODA

Auto-tabling for subproblem presolving in MiniZinc

Dekker, Jip and Björdal, Gustav and Carlsson, Mats and Flener, Pierre and Monette, Jean-Noël (2017) Auto-tabling for subproblem presolving in MiniZinc. Constraints, 22 (4). pp. 512-529. ISSN 1383-7133 (Print) 1572-9354 (Online)

Full text not available from this repository.

Official URL: https://link.springer.com/article/10.1007/s10601-0...

Abstract

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.

Item Type:Article
ID Code:6160
Deposited By:Mats Carlsson
Deposited On:14 Sep 2017 09:25
Last Modified:14 Sep 2017 09:25

Repository Staff Only: item control page