Enhancing interval constraint propagation by identifying and filtering n-ary subsystems

Ignacio Araya, Victor Reyes

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


When interval branch and bound solvers are used for solving numerical constraint satisfaction problems, constraint propagation algorithms are commonly used for filtering/contracting the variable domains. However, these algorithms suffer from the locality problem which is related to the reduced scope of local consistencies. In this work we propose a preprocessing and a filtering technique to reduce the locality problem and to enhance the contraction power of constraint propagation algorithms. The preprocessing consists in constructing a directed acyclic graph (DAG) by merging equivalent nodes (or common subexpressions) and identifying subsystems of n-ary sums in the DAG. The filtering technique consists in applying iteratively HC4 and an ad-hoc technique for contracting the subsystems until reaching a fixed point. Experiments show that the new approach outperforms state-of-the-art strategies using a well known set of benchmark instances.

Original languageEnglish
Pages (from-to)1-20
Number of pages20
JournalJournal of Global Optimization
Issue number1
StatePublished - 15 May 2019


  • Common subexpression elimination
  • Constraint propagation
  • Interval-based solver
  • Systems of nonlinear equations


Dive into the research topics of 'Enhancing interval constraint propagation by identifying and filtering n-ary subsystems'. Together they form a unique fingerprint.

Cite this