*irreducible infeasible subsystems*(IISes) and feasOpt() to find a “cheapest” relaxation of constraints and bounds that makes the model feasible. They also provide access to what is known as a

*Farkas certificate*.

Thanks to Bo Jensen, who reminded me about Farkas certificates in a comment yesterday. He also provided a link to MOSEK's description of them, which saves me quite a bit of typing. Farkas certificates draw their name from Farkas's lemma, a well-known result in linear programming theory. While it is possible for both a primal linear program and its dual to be infeasible, that condition is rare in practice. The (much) more common case is that an infeasible LP has an unbounded dual. In essence, a Farkas certificate is a recession direction for the dual problem. It's existence proves the infeasibility of the primal.

For infeasible LPs, CPLEX provides the IloCplex.dualFarkas() method to get a Farkas certificate. (As always, I'll stick to the Java API, but all the APIs should provide some version of this.) The method has two arguments used for returning results (and

*not*for providing inputs). One argument returns a list of primal constraints with non-zero dual values; the other vector holds the corresponding dual values.

Continuing yesterday's Java code (without repeating it), I'll start by constructing the new primal problem:

```
IloCplex primal = new IloCplex();
IloNumVar u = primal.numVar(0, Double.MAX_VALUE, "u");
IloNumVar v = primal.numVar(0, Double.MAX_VALUE, "v");
IloNumVar w = primal.numVar(0, Double.MAX_VALUE, "w");
IloNumVar[] vars = new IloNumVar[] {u, v, w};
primal.addMinimize(
primal.scalProd(new double[] {1.0, 1.0, -2.0}, vars));
IloConstraint c1 =
primal.addGe(
primal.scalProd(new double[] {1.0, -2.0, -1.0}, vars),
3.0);
IloConstraint c2 =
primal.addGe(
primal.scalProd(new double[] {-2.0, 1.0, -1.0}, vars),
2.0);
```

Since I cannot be sure which constraints dualFarkas will return, nor in what order, it will be handy to construct a map associating each constraint with the corresponding dual variable.

```
HashMap<IloConstraint, IloNumVar> map =
new HashMap<IloConstraint, IloNumVar>();
map.put(c1, x);
map.put(c2, y);
```

Now I turn off the presolver, solve the model, and verify that it is infeasible. (As was the case yesterday with an unbounded primal, fail to turn off the presolver will cause CPLEX to throw an exception when I try to access the Farkas certificate.) I also need to use the dual simplex algorithm; any other algorithm (primal simplex, barrier, ...) will cause CPLEX to throw an exception. There is no explicit statement in the code since CPLEX's default choice for algorithm

*on this problem*is dual simplex, but in general it should probably be specified just in case CPLEX prefers some other algorithm.

```
primal.setParam(IloCplex.BooleanParam.PreInd, false);
primal.solve();
System.out.println("CPLEX status: "
+ primal.getCplexStatus());
```

The next step is to access the Farkas certificate:

```
IloRange[] farkasConstraints = new IloRange[2];
double[] farkasValues = new double[2];
primal.dualFarkas(farkasConstraints, farkasValues);
System.out.print("Farkas certificate:");
for (int i = 0; i < 2; i++) {
System.out.print("\t" + map.get(farkasConstraints[i])
+ " -> " + farkasValues[i]);
}
System.out.println("");
```

To find the vertex at which it is anchored, I can access the last feasible dual solution obtained before CPLEX stopped.

```
double[] q = primal.getDuals(farkasConstraints);
System.out.print("Dual vertex:");
for (int i = 0; i < 2; i++) {
System.out.print("\t" + map.get(farkasConstraints[i])
+ " -> " + q[i]);
}
System.out.println("");
```

I still have one concern. The definition of a Farkas certificate only guarantees a recession direction for the dual; it does not need to be an extreme dual direction to qualify as a Farkas certificate. I suspect, but do not know with certainty, that the mechanism by which solvers select a Farkas certificate will consistently lead to an extreme direction.