The idea with Max Separation Distance is to get the term for which the maximum discrepancy between the relaxation and the original problem is the largest. Then, for the variables in the aforementioned terms, a hybrid-integer-least-reduced-axis approach is applied.
The motivation behind this is to only perform hybrid integer least reduce axis to the subset of variables that appear in the term most likely to cause discrepancy, between upper and lower bounding solutions. This method does not require the solution of optimisation problems.
The procedure for calculating separation distances between terms and their respective relaxations is term-type specific:
- Bilinear terms of the form \({xy,x\in[x_{lb},x_{ub}],y\in[y_{lb},y_{ub}]}\): the maximum separation distance for such terms is given by \({0.25(x_{ub}-x_{lb})(y_{ub}-y_{lb})}\).
- General non-convex terms for each \({x\in[x_{lb},x_{ub}]}\): the maximum separation distance for such terms is given by \({0.25\alpha(x_{ub},x_{lb})(x_{ub}-x_{lb})^2}\).
Note that in this case, multivariate terms can be handled. Therefore, a summation of separation distances for all participating variables in the term takes place. The issue here can be the definition of \(\alpha(x_{ub},x_{lb})\). Further information and references about this are included towards the end of the article so keep reading.
By repeating the process for all terms, the maximum separation distances are calculated. It is then straightforward to find the term with the largest maximum separation distance. If the term is univariate, the associated variable is chosen as a branching variable.
Regarding the parameter \(\alpha\):
A generic definition of the \(\alpha\) parameter is provided here. For further information, you can look into:
- Appendix A 2 of Maranas, C.D., Floudas, C.A. Global minimum potential energy conformations of small molecules. J Glob Optim 4, 135–170 (1994). https://doi.org/10.1007/BF01096720
- Androulakis, I.P., Maranas, C.D. & Floudas, C.A. αBB: A global optimization method for general constrained nonconvex problems. J Glob Optim 7, 337–363 (1995). https://doi.org/10.1007/BF01099647
- https://en.wikipedia.org/wiki/ΑΒΒ
Now let \(V\) be a general non-convex term. Now let \(x^i\in[x^i_{lb},x^i_{ub}]\) be the variables participating in this non-convex term. Furthermore, let \(\lambda_i\) be the eigenvalues of the Hessian matrix of \(V\).
Due to the general nonlinearity of \(V\), these eigenvalues are a function of \(x^i\). The \(\alpha\) parameter is then defined as follows:
\[
\begin{equation}
\alpha = \max\left\{0,\max_{{i \atop x^i_{lb} \leq x^i \leq x^i_{ub}}} (-\frac{1}{2}\lambda_i(x^i))\right\}
\nonumber
\end{equation}
\]
The challenge of calculating \(\alpha\) can be alleviated by a series of approximations. Further information on which can be found in the sources provided above.