Most Violated Term

What is Most Violated Term?
Putting this into Practice
Option associated with Most Violated Term

What is Most Violated Term?

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. This method does not require the solution of optimisation problems and shows the greatest computational efficiency in Octeract Engine. Therefore, it is the Default variable selection heuristic.

Putting this into Practice

Now let’s assume that we are testing variable \({x\in[x_{lb},x_{ub}]}\). Now 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)=0.17442}\).

Option Associated with Most Violated Term