Optimization Online


Rigorous global filtering methods with interval unions

Ferenc Domes(ferenc.domes***at***univie.ac.at)
Tiago Montanher(tiago.de.morais.montanher***at***univie.ac.at)
Hermann Schichl(hermann.schichl***at***univie.ac.at)
Arnold Neumaier(arnold.neumaier***at***univie.ac.at)

Abstract: This paper presents rigorous filtering methods for constraint satisfaction problems based on the interval union arithmetic. Interval unions are finite sets of closed and disjoint intervals that generalize the interval arithmetic. They allow a natural representation of the solution set of interval powers, trigonometric functions and the division by intervals containing zero. We show that interval unions are useful when applied to the forward-backward constraint propagation on directed acyclic graphs (DAGs) and can also replace the interval arithmetic in the Newton operator. Empirical observations support the conclusion that interval unions reduce the search domain even when more expensive state-of-the-art methods fail. Interval unions methods tend to produce a large number of boxes at each iteration. We address this problem by taking a suitable gap-filling strategy. Numerical experiments on constraint satisfaction problems from the COCONUT test set show the capabilities of the new approach.

Keywords: Interval arithmetic; Constraint propagation; Interval Newton method; Global optimization

Category 1: Global Optimization

Citation: To appear in Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy, etc. Methods and Their Applications (O. Kosheleva, et al., eds.) (2018).

Download: [PDF]

Entry Submitted: 04/03/2018
Entry Accepted: 04/03/2018
Entry Last Modified: 04/03/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society