Originally posted by: SystemAdmin
CPXdualfarkas() is somewhat tricky to understand. The method provides a set of dual multipliers y', such that the aggregated row y'Ax >= y'b is a valid inequality (the signs of y' match the inequality sense of the constraints) that proves infeasibility of the system. Namely, this aggregated row a'x >= b' cannot be made feasible even if you substitute the "most feasible" bound of x_j for each variable x_j. In other words, max{a'x | l <= x <= u} < b'. In this sense, y' is not a dual ray (because y'A does not need to be 0), but you can extend it with suitable reduced cost values (i.e., duals for the bounds) to a dual ray.
For example, consider the following system:
1x1 + 3x2 - 2x3 >= 5
1x1 - 4x2 + 4x3 >= 6
with bounds 0 <= x1 <= 3, 0 <= x2 <= 5, 0 <= x3 <= 1.
Then, the dual vector y'=(1,2) yields the aggregated row y'Ax >= y'b that reads
3x1 - 5x2 + 6x3 >= 17.
This shows the infeasibility of the model, because substituting the "most feasible" bounds for x yields
3*3 - 5*0 + 6*1 = 15 < 17.
Now, if you extend the dual vector y' with reduced costs r' = (-3,5,-6), you get a dual ray:
1x1 + 3x2 - 2x3 >= 5 (y'_1 = 1)
1x1 - 4x2 + 4x3 >= 6 (y'_2 = 2)
x1 <= 3 (r'_1 = -3)
x2 >= 0 (r'_2 = 5)
x3 <= 1 (r'_3 = -6)
Summing this up with the weights of the dual ray yields
0x1 + 0x2 + 0x3 >= 2,
which proves the infeasibility of the model.
#CPLEXOptimizers#DecisionOptimization