A contractor based on convex interval Taylor

IGNACIO DANIEL ARAYA ZAMORANO, Gilles Trombettoni, Bertrand Neveu

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

35 Scopus citations

Abstract

Interval Taylor has been proposed in the sixties by the interval analysis community for relaxing continuous non-convex constraint systems. However, it generally produces a non-convex relaxation of the solution set. A simple way to build a convex polyhedral relaxation is to select a corner of the studied domain/box as expansion point of the interval Taylor form, instead of the usual midpoint. The idea has been proposed by Neumaier to produce a sharp range of a single function and by Lin and Stadtherr to handle n x n (square) systems of equations. This paper presents an interval Newton-like operator, called X-Newton, that iteratively calls this interval convexification based on an endpoint interval Taylor. This general-purpose contractor uses no preconditioning and can handle any system of equality and inequality constraints. It uses Hansen's variant to compute the interval Taylor form and uses two opposite corners of the domain for every constraint. The X-Newton operator can be rapidly encoded, and produces good speedups in constrained global optimization and constraint satisfaction. First experiments compare X-Newton with affine arithmetic.

Original languageEnglish
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 9th International Conference, CPAIOR 2012, Proceedings
Pages1-16
Number of pages16
DOIs
StatePublished - 29 May 2012
Event9th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2012 - Nantes, France
Duration: 28 May 20121 Jun 2012

Publication series

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

Conference

Conference9th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2012
CountryFrance
CityNantes
Period28/05/121/06/12

Fingerprint Dive into the research topics of 'A contractor based on convex interval Taylor'. Together they form a unique fingerprint.

Cite this