CPXXdualfarkas and CPXdualfarkas
The routine CPXXdualfarkas/CPXdualfarkas assumes that there is a resident
solution as produced by a call to CPXXdualopt/CPXdualopt and that the
status of this solution as returned by CPXXgetstat/CPXgetstat is
CPX_STAT_INFEASIBLE.
int CPXXdualfarkas( CPXCENVptr env, CPXCLPptr lp, double * y, double * proof_p )
int CPXdualfarkas( CPXCENVptr env, CPXCLPptr lp, double * y, double * proof_p )
Description
This is an advanced routine. Advanced routines typically demand a thorough understanding of the algorithms used by CPLEX. Thus they incur a higher risk of incorrect behavior in your application, behavior that can be difficult to debug. Therefore, the team encourages you to consider carefully whether you can accomplish the same task by means of other Callable Library routines instead.
The routine CPXXdualfarkas/CPXdualfarkas assumes that there is a resident
solution as produced by a call to CPXXdualopt/CPXdualopt and that the
status of this solution as returned by CPXXgetstat/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 righthand-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.
Arguments
- env
-
A pointer to the CPLEX environment, as returned by
CPXXopenCPLEX/CPXopenCPLEX. - lp
-
A pointer to a CPLEX LP problem object, as returned by
CPXXcreateprob/CPXcreateprob. - y
- An array of doubles of length at least equal to the number of rows in the problem.
- proof_p
-
A pointer to a double. The argument
proof_pis allowed to have the value NULL.