Exploiting common subexpressions in numerical CSPs

IGNACIO DANIEL ARAYA ZAMORANO, Bertrand Neveu, Gilles Trombettoni

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

18 Scopus citations

Abstract

It is acknowledged that the symbolic form of the equations is crucial for interval-based solving techniques to efficiently handle systems of equations over the reals. However, only a few automatic transformations of the system have been proposed so far. Vu, Schichl, Sam-Haroud, Neumaier have exploited common subexpressions by transforming the equation system into a unique directed acyclic graph. They claim that the impact of common subexpressions elimination on the gain in CPU time would be only due to a reduction in the number of operations. This paper brings two main contributions. First, we prove theoretically and experimentally that, due to interval arithmetics, exploiting certain common subexpressions might also bring additional filtering/contraction during propagation. Second, based on a better exploitation of n-ary plus and times operators, we propose a new algorithm I-CSE that identifies and exploits all the "useful" common subexpressions. We show on a sample of benchmarks that I-CSE detects more useful common subexpressions than traditional approaches and leads generally to significant gains in performance, of sometimes several orders of magnitude.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - 14th International Conference, CP 2008, Proceedings
Pages342-357
Number of pages16
DOIs
StatePublished - 26 Nov 2008
Event14th International Conference on Principles and Practice of Constraint Programming, CP 2008 - Sydney, NSW, Australia
Duration: 14 Sep 200818 Sep 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5202 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Principles and Practice of Constraint Programming, CP 2008
CountryAustralia
CitySydney, NSW
Period14/09/0818/09/08

Fingerprint Dive into the research topics of 'Exploiting common subexpressions in numerical CSPs'. Together they form a unique fingerprint.

Cite this