The routine CPXdualfarkas assumes that there is a resident solution as produced by a call to CPXdualopt and that the status of this solution as returned by CPXgetstat is CPX_STAT_INFEASIBLE.

The values returned in the array y[] have the following interpretation. For the ith constraint, if that constraint is a less-than-or-equal-to constraint, y[i]≤ 0 holds; if that constraint is a greater-than-or-equal-to constraint, y[i]≥ 0 holds. Thus, where b is the right-hand-side vector for the given linear program, A is the constraint matrix, and x denotes the vector of variables, y may be used to derive the following valid inequality:

yTA x ≥ yTb

Here y is being interpreted as a column vector, and yT denotes the transpose of y.

The real point of computing y is the following. Suppose we define a vector z of dimension equal to the dimension of x and having the following value for entries

zj = uj where yTAj > 0, and

zj = lj where yTAj < 0,

where Aj denotes the column of A corresponding to xj, uj the given upper bound on xj, and lj is the specified lower bound. (zj is arbitrary if yTAj = 0.) Then y and z will satisfy

yTb - yTA z > 0.

This last inequality contradicts the validity of yTA x ≥ yTb, and hence shows that the given linear program is infeasible. The quantity *proof_p is set equal to yTb - yTA z. Thus, *proof_p in some sense denotes the degree of infeasibility.