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

Ignacio Araya () and Victor Reyes ()
Additional contact information
Ignacio Araya: Pontificia Universidad Católica de Valparaíso
Victor Reyes: Pontificia Universidad Católica de Valparaíso

Journal of Global Optimization, 2019, vol. 74, issue 1, No 1, 20 pages

Abstract: 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.

Keywords: Interval-based solver; Common subexpression elimination; Constraint propagation; Systems of nonlinear equations (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-019-00738-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:74:y:2019:i:1:d:10.1007_s10898-019-00738-5

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-019-00738-5

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().