Hybridizing two linear relaxation techniques in interval-based solvers

Ignacio Araya (), Frédéric Messine (), Jordan Ninin () and Gilles Trombettoni ()
Additional contact information
Ignacio Araya: Pontificia Universidad Católica de Valparaíso
Frédéric Messine: University of Toulouse, ENSEEIHT-LAPLACE, CNRS
Jordan Ninin: ENSTA-Bretagne, Lab-STICC, team MATRIX
Gilles Trombettoni: University of Montpellier, CNRS

Journal of Global Optimization, 2025, vol. 91, issue 3, No 1, 437-456

Abstract: Abstract In deterministic global optimization, techniques for linear relaxation of a non-convex program are used in the lower bound calculation phase. To achieve this phase, most deterministic global optimization codes use reformulation-linearization techniques. However, there exist also two interval-based polyhedral relaxation techniques which produce reliable bounds without adding new auxiliary variables, and which can take into account mathematical operations and most transcendental functions: (i) the affine relaxation technique, used in the IBBA code, based on affine forms and affine arithmetic, and (ii) the extremal Taylor technique, used in the Ibex-Opt code, which is based on a specific interval-based Taylor form. In this paper, we describe how these two interval-based linear relaxation techniques can be hybridized. These two approaches appear to be complementary, and such a hybrid method performs well on a representative sample of constrained global optimization instances.

Keywords: Interval analysis; Global optimization; Linear relaxation; Reliable computing; Branch-and-bound (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-024-01449-2 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:91:y:2025:i:3:d:10.1007_s10898-024-01449-2

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

DOI: 10.1007/s10898-024-01449-2

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 ().