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

Ignacio Araya, Victor Reyes

Research output: Contribution to journalArticlepeer-review

Abstract

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
JournalJournal of Global Optimization
Volume74
Issue number1
DOIs
StatePublished - 15 May 2019
Externally publishedYes

Keywords

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

Fingerprint

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