On branching-point selection for triple products in spatial branch-and-bound: the hull relaxation

Emily Speakman, Jon Lee

Published 2017-06-26Version 1

Speakman and Lee analytically developed the idea of using volume as a measure for comparing relaxations in the context of spatial branch-and-bound. Specifically, for trilinear monomials, they analytically compared the three possible "double-McCormick relaxations" with the tight convex-hull relaxation. Here, again using volume as a measure, for the convex-hull relaxation of trilinear monomials, we establish simple rules for determining the optimal branching variable and optimal branching point. Additionally, we compare our results with current practice in software.