Hybridizing two linear relaxation techniques in interval-based solvers

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.