FarkasDual

Type: double
Modifiable: No

Together, attributes FarkasDual and FarkasProof provide a certificate of infeasibility for the given infeasible problem. Specifically, FarkasDual provides a vector <span>$</span>\lambda<span>$</span> that can be used to form the following inequality from the original constraints that is trivially infeasible within the bounds of the variables:

<span>$</span>\lambda^tAx \leq \lambda^tb.<span>$</span>

This inequality is valid even if the original constraints have a mix of less-than and greater-than senses because <span>$</span>\lambda_i \geq 0<span>$</span> if the <span>$</span>i<span>$</span>-th constraint has a <span>$</span>\leq<span>$</span> sense and <span>$</span>\lambda_i \leq 0<span>$</span> if the <span>$</span>i<span>$</span>-th constraint has a <span>$</span>\geq<span>$</span> sense.

Let

<span>$</span>\bar{a} := \lambda^tA<span>$</span>

be the coefficients of this inequality and

<span>$</span>\bar{b} := \lambda^tb<span>$</span>

be its right hand side. With <span>$</span>L_j<span>$</span> and <span>$</span>U_j<span>$</span> being the lower and upper bounds of the variables <span>$</span>x_j<span>$</span>, we have <span>$</span>\bar{a}_j \geq 0<span>$</span> if <span>$</span>U_j = \infty<span>$</span>, and <span>$</span>\bar{a}_j \leq 0<span>$</span> if <span>$</span>L_j = -\infty<span>$</span>.

The minimum violation of the Farkas constraint is achieved by setting <span>$</span>x^*_j := L_j<span>$</span> for <span>$</span>\bar{a}_j > 0<span>$</span> and <span>$</span>x^*_j := U_j<span>$</span> for <span>$</span>\bar{a}_j < 0<span>$</span>. Then, we can calculate the minimum violation as

<span>$</span>\beta := \bar{a}^tx^* - \bar{b} =
\sum\limits_{j:\bar{a}_j>0}\bar{a}_jL_j + \sum\limits_{j:\bar{a}_j<0}\bar{a}_jU_j - \bar{b}<span>$</span>

where <span>$</span>\beta>0<span>$</span>.

The FarkasProof attribute gives the value of <span>$</span>\beta<span>$</span>.

These attributes are only available when parameter InfUnbdInfo is set to 1.

For examples of how to query or modify attributes, refer to our Attribute Examples.