The idea behind Most Violated Term branching is to select the variable that causes the biggest discrepancy between the original nonlinear terms of the problem and its relaxation.
Let’s assume that we are testing variable \({x\in[x_{lb},x_{ub}]}\). Let the variable at hand appear in a nonlinear function in the original model, say \({f(x)}\). In the relaxation procedure \(f(x)\) is linearised and replaced with an underestimator. Let the latter be \(f_{lin}(x)\).
It’s important to note that this happens for all nonlinear terms in the problem thus causing the relaxation of the problem to be created. Let \({x^*}\) be the solution of the relaxation at the current Node where branching needs to be performed.
Since \(f_{lin}(x)\) is only an underestimator of \(f(x)\), a discrepancy between the underestimator and the original function, at the solution of the relaxation, will occur. The discrepancy is defined as \(f(x^*)-f_{lin}(x^*)\) and it’s non-negative. The value of the discrepancy, a.k.a. the violation, is assigned to the variable.
The variable accumulates non-negative violations from all nonlinear terms that it appears in.
By repeating the process for all variables, the accumulated violations are calculated. It is then straightforward to find the variable with the largest discrepancy or, in other words, the variable that causes the most violated terms.
Note that during the procedure the violation of two variables may be equally the largest. In this case, the tie will be broken using other branching techniques, only for the tied variables.
To demonstrate, here’s a simple example: Take \(\log(x),x\in[2,4]\) and its underestimator \(\frac{\log(4)}{3}(x-1)\). Suppose that \(x^*=3\). The violation for \(x\) associated with this term is simply \({\log(x^*)-\frac{\log(4)}{3}(x^*-1)\approx{0.076}}\).