Violation Transfer

What is Violation Transfer?

The idea is to estimate the impact of a variable on the current status of the problem, when all other variables are fixed.

Let’s assume that the original problem at hand is \({\min\{f(x) : g_i(x) \leq 0, i\in I\}}\), \({\min\{\bar{f}(x): \bar{g}_i(x) \leq 0, i\in H\}}\) is its linear underestimator and \(x^*\) the solution vector of the aforementioned underestimator. The non-negative Lagrange multipliers, associated with the solution of the undertimator, are denoted as \(\lambda^*_i\) for constraint \(\bar{g}_i\leq 0\).

The Lagrangian function of the underestimator is defined as \({L(x)=\bar{f}(x)+\sum_{i \in H}\lambda_i\bar{g}_i(x)}\). Since the underestimator is linear, you can pose the Lagrangian function as \({L(x)=\bar{f}(x)+\sum_{i \in H}\lambda_i(\sum_{j \in J}{a_{i,j}x_j}+b_i)}\).

For a variable \(x_j\in[{x^j_{lb},x^j_{ub}]}\) with an optimal solution at the relaxation of \(x^*_j\), an interval is sought such that all other variables \(x_k, k \in J, j\neq k\) are still feasible for at least one point in that interval. Now let that interval be \({[x^j_{vl}, x^j_{vu}]}\). Also, let the length of the interval be defined as \(\gamma_j = x^j_{vu}-x^j_{vl}\).

An estimate of the change of the underestimator’s solution value for variable \(x_j\) can then be calculated as: \({\gamma_j|\sum_{i \in H}\lambda^*_ia_{i,j}|}\). By repeating the process for all variables, the accumulated violations are calculated.

It is then straightforward to find the variable with the largest Violation Transfer. Or, in other words, the variable that is more likely to positively impact the lower bounding solution of the problem \({\min\{f(x) : g_i(x) \leq 0, i\in I\}}\).

Putting this into Practice

A simple example: take the nonlinear function \(y\geq x^2\)for \(x \in [-2, 2.5]\) and \(y \in [0, 8]\). Let’s assume that this function is linearised in three points. Namely, the lower and upper bounds of \(x\) and their midpoint. In Figure 1, \(x\) and \(y\) are denoted by the axes, the original feasible region is shown in orange and the linear approximation of the region in grey dashed lines.

Let’s assume that this nonlinear function is part of an optimisation problem. Let’s also assume that the solution of the relaxation of this problem yields the values \(x^*=1\) and \(y^*=2\).

It is clear that the bounds of \(x\) in the original problem are between \(-2\) and \(2.5\). If we attempt to keep the value for \(y\) fixed at the solution \(y^*=2\) then it is clear that the smallest interval of \(x\) that we can derive for which the solution \(x^*=1\) and \(y^*=2\) is feasible is \([-\sqrt{2},\sqrt{2}]\) (range depicted in green colour). Therefore, in this example, \(\gamma_x = 2\sqrt{2}\).

A less complicated approach, although approximate, would be to determine \(\gamma_x\) based on the relaxation (i.e. the grey dashed lines). In this case, \(\gamma_x = 3.15\) (Figure 2).

More information regarding the Violation Transfer branching method can be found in: Tawarmalani, M., Sahinidis, N. V., Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Mathematical Programming, 99(3):563-591, 2004

Figure 1: exact calculation
Figure 1: Exact calculation of interval \(\gamma\)
Figure 2: approximate calculation
Figure 2: Approximate calculation of interval \(\gamma\)

Was this helpful?
Please make sure you fill the comments section before sending.

Thank you for your comments.
Please contact us if you need any further support.