If ILOG CPLEX reports that your problem is infeasible, then you should invoke the ILOG CPLEX infeasibility finder to save time and effort in the development process. This diagnostic tool computes a set of infeasible constraints and column bounds that would be feasible if one of them (a constraint or variable) were removed. Such a set is known as an irreducibly inconsistent set (IIS).

To work, the infeasibility finder must have a problem that satisfies two conditions:

• the problem has been optimized using the primal simplex optimizer or barrier with primal crossover, and
• the problem has terminated with an infeasible basic solution to the primal problem.

When the ILOG CPLEX presolver detects infeasibility during preprocessing, no optimization has yet taken place. Furthermore, since the presolver may perform many passes on a problem, the reason that it identifies a row as infeasible may not be obvious. To run the infeasibility finder and to see solution statistics in such a case, you should first turn off ILOG CPLEX preprocessing before you optimize, as explained in Preprocessing, before you invoke the infeasibility finder.

The barrier optimizer may be called with primal crossover, dual crossover, or no crossover. Only the primal crossover options will allow you to subsequently run the infeasibility finder.

The parameter IISInd controls the method used for determining the IIS. Its default value of 0 (zero) invokes an algorithm that requires minimal computation time but may generate a large set of inconsistent constraints.

To invoke the infeasibility finder and to display part of its findings in the Interactive Optimizer, use the command display iis. By default, ILOG CPLEX records all its findings in a log file. To send these findings to your screen as well, use the command set output logonly y cplex.log.

You can also write an IIS file from the Interactive Optimizer and then examine it with your preferred text editor to see all the constraints and bounds in the irreducibly inconsistent set.

For an example of how to use the infeasibility finder and how to interpret its results, see Example: Output from the Infeasibility Finder in the Interactive Optimizer.

Its alternative value of 1 (one) may take longer but generates a minimal set of irreducibly inconsistent constraints. Use the method cplex.out() or the routines CPXdisplayiis() or CPXiiswrite() to output the results for review.

The infeasibility finder will find only one irreducibly inconsistent set (IIS), though a given problem may contain many independent IISs. Consequently, even after you detect and correct one such IIS in your problem, it may still remain infeasible. In such a case, you need to run the infeasibility finder more than once to detect those multiple causes of infeasibility in your problem.

After you have optimized a problem and ILOG CPLEX has terminated with a primal infeasible basic solution, then you can invoke the ILOG CPLEX infeasibility finder on this optimized problem and its infeasible basic solution. The ILOG CPLEX infeasibility finder will compute an IIS of constraints and column bounds from your problem and record this IIS in a log file along with other useful information to help you locate the source of infeasibility and aid in revising or reformulating your model.

If you want ILOG CPLEX to display this additional information on your screen in the Interactive Optimizer, use the command set output logonly yes. After that command, invoke the infeasibility finder with the command display iis. ILOG CPLEX will respond like this:

Starting Infeasibility Finder Algorithm... Performing row sensitivity filter Performing column sensitivity filter Number of rows in the iis: 3 Number of columns in the iis: 3 Names of rows in the iis: NODE5 (fixed) D7 (lower bound) D8 (lower bound) Names of columns in the iis: T25 (upper bound) T35 (upper bound) T47 (upper bound) Iis Computation Time = 0.01 sec.

As you can see, ILOG CPLEX states how many rows and columns comprise the IIS. It also displays the row and column names, and it identifies the bound causing the infeasibility. In this example, all the columns in the IIS are limited by their upper bound. If you remove any of the upper bounds on those columns, then the IIS becomes feasible. The bound information about rows is really needed only for ranged rows. In the case of ranged rows, the bound indicates whether the row lies at the lower or upper end of the range of right-hand side values. For other kinds of rows, there is only one possible right-hand side value at which the row can lie. Greater-than constraints must lie at their lower bound. Less-than constraints must lie at their upper bound. Equality constraints are fixed.

After you have invoked the infeasibility finder with the display iis command, if you want additional information to determine the cause of infeasibility, use the write command and the file type iis to generate a ILOG CPLEX LP format file containing each individual constraint and bound in the IIS. You can then use the xecute command to call an ordinary text editor during your ILOG CPLEX session to examine the contents of that IIS file. It will look something like this example:

CPLEX> write infeas.iis Starting Infeasibility Finder Algorithm... Performing row sensitivity filter Performing column sensitivity filter Irreducibly inconsistent set written to file `infeas.iis'. CPLEX> xecute edit infeas.iis Minimize subject to \Rows in the iis: NODE5: T25 + T35 - T57 - T58 = 0 D7: T47 + T57 >= 20 D8: T58 >= 30 \Columns in the iis: Bounds T25 <= 10 T35 <= 10 T47 <= 2 \Non-iis columns intersecting iis rows: T57 Free T58 Free

In this example, you see that the bounds on T25 and T35 combine with the row NODE5 to imply that

. However, row D7 and the bound on T47 imply that

. Since row D8 requires

, we see that

, so the constraints and bounds are infeasible. Notice that every constraint and bound contributes to this infeasibility, according to the definition of an IIS. There are, in consequence, many different ways to modify such a problem to make it feasible. The "right" change will depend on your knowledge of the problem.

When ILOG CPLEX records the constraints and bounds of an IIS, it also lists as free all columns that intersect one or more rows in the IIS but do not have bounds in the IIS. This portion of the file ensures that when you read the file into ILOG CPLEX, the resulting problem satisfies the definition of an IIS. After you read in such a file, you can perform additional problem analysis within your ILOG CPLEX session.

In the example that we have been looking at, there were sufficiently few row and column bounds in the IIS for us to see the cause of infeasibility at a glance. In contrast, other IIS files may contain so many rows and columns that it becomes difficult to see the cause of infeasibility. When an IIS contains many equality constraints and only a few bounds, for example, this phenomenon commonly occurs. In such a situation, the equality constraints transfer the infeasibility from one part of the model to another until eventually no more transfers can occur. Consequently, such an IIS file will also contain a cumulative constraint consisting of the sum of all the equality rows. This cumulative constraint can direct you toward the cause of infeasibility, as the following sample IIS illustrates:

Minimize subject to \Rows in the iis: 2: - x24 + x97 + x98 - x99 - x104 = -7758 3: - x97 + x99 + x100 - x114 - x115 = 0 4: - x98 + x104 = 0 10: - x105 + x107 + x108 - x109 = -151 11: - x108 + x109 + x110 - x111 = -642 12: - x101 - x102 - x110 + x111 + x112 + x113 - x117 = -2517 13: - x112 + x117 + x118 - x119 = -186 14: - x118 + x119 + x120 + x121 - x122 - x123 = -271 15: - x120 + x122 = -130 16: - x121 + x123 + x124 - x125 = -716 17: - x124 + x125 + x126 - x127 = -2627 18: - x126 + x127 + x128 - x129 = -1077 19: - x128 + x129 + x130 - x131 = -593 249: - x100 + x101 + x103 = 0 251: - x113 + x114 + x116 = 0 \Sum of equality rows in iis: \ - x24 - x102 + x103 - x105 + x107 - x115 + x116 + x130 - x131 = -16668 \Columns in the iis: Bounds x24 <= 14434 x102 = 0 x103 = 0 x105 = 0 x107 = 0 x115 = 0 x116 = 0 x130 = 0 x131 = 0 \Non-iis columns intersecting iis rows: x97 Free x98 Free x99 Free . . . End

Since there are 15 rows in this IIS file, the cause of infeasibility is not immediately obvious. However, if we look at the sum of the bounds on the columns, we see that

, so it is impossible to satisfy the sum of equality rows. Therefore, to correct the infeasibility, we must alter one or more of the bounds, or we must increase one or more of the right-hand side values.

The ILOG CPLEX infeasibility finder will stop when its total runtime exceeds the limit set by the command set timelimit. The infeasibility finder works by removing constraints and bounds that cannot be involved in the IIS, so it can provide partial information about an IIS when it reaches its time limit. The collection of constraints and bounds it offers then do not strictly satisfy the definition of an IIS. However, the collection does contain a true IIS within it, and frequently it provides enough information for you to diagnose the cause of infeasibility in your problem. When it reaches the time limit, ILOG CPLEX output indicates that it has found only a partial IIS. The following example illustrates this idea. In it, we set a time limit and then invoke the feasibility finder.

CPLEX> set timelimit 2 CPLEX> display iis Starting Infeasibility Finder Algorithm... Performing row sensitivity filter Infeasibility Finder Algorithm exceeded time limit. Partial infeasibility output available. Number of rows in the (partial) iis: 101 Number of columns in the (partial) iis: 99

The size of the IIS reported by ILOG CPLEX depends on many factors in the model. If an IIS contains hundreds of rows and columns, you may find it hard to determine the cause of the infeasibility. Fortunately, there are tactics to help you interpret IIS output:

• Consider selecting an alternative IIS algorithm. The default algorithm emphasizes computation speed, and it may give rise to a relatively large IIS. If so, try setting the IISInd parameter to 1 (one) to invoke the alternative algorithm, and then run the infeasibility finder again. Normally, the resulting IIS is smaller because the alternative algorithm emphasizes finding a minimal IIS at the expense of computation speed.
• If the problem contains equality constraints, examine the cumulative constraint consisting of the sum of the equality rows. As we illustrated in one of the examples, the cumulative constraint can simplify your interpretation of the IIS output. More generally, if you take other linear combinations of rows in the IIS, that may also help. For example, if you add an equality row to an inequality row, the result may yield a simpler inequality row.
• Try preprocessing with the ILOG CPLEX presolver and aggregator. The presolver may even detect infeasibility by itself. If not, running the infeasibility finder on the presolved problem may help by reducing the problem size and removing extraneous constraints that do not directly cause the infeasibility but still appear in the IIS. Similarly, running the infeasibility finder on an aggregated problem may help because the aggregator performs substitutions that may remove extraneous variables that clutter the IIS output. More generally, if you perform substitutions, you may simplify the output so that it can be interpreted more easily.
• Other simplifications of the constraints in the IIS, such as combining variables, multiplying constraints by constants, and rearranging sums, may make it easier to interpret the IIS.