Finding a Set of Irreducibly Inconsistent Constraints
PREVIOUS
NEXT
| > Continuous Optimization > Solving LPs: Simplex Optimizers > Diagnosing LP Infeasibility > Finding a Set of Irreducibly Inconsistent Constraints |
Finding a Set of Irreducibly Inconsistent Constraints |
INDEX
PREVIOUS
NEXT
|
If ILOG CPLEX reports that your problem is infeasible, then you can invoke the ILOG CPLEX infeasibility finder to help you analyze the source of the infeasibility. 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 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.
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.
After that command, invoke the infeasibility finder with the command display iis. ILOG CPLEX will respond like this:
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:
In this example, you see that the bounds on T25 and T35 combine with the row NODE5 to imply that T57 + T58 <= 20. However, row D7 and the bound on T47 together imply that T57 >= 18. Since row D8 requires that T58 >= 30, you see that T57 + T58 >= 48, 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 makes sure 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 presented thus far, there were sufficiently few row and column bounds in the IIS 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:
Since there are 15 rows in this IIS file, the cause of infeasibility is not immediately obvious. However, if you look at the sum of the bounds on the columns, you see that
-x24 -x102 + x103 -x105 +x107 -x115 +x116 + x130 -x131 >= -14434
so it is impossible to satisfy the sum of equality rows. Therefore, to correct the infeasibility, you must alter one or more of the bounds, or you 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. It sets a time limit and then invokes the feasibility finder.
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:
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.
| Copyright © 1987-2003 ILOG, S.A. All rights reserved. Legal terms. | PREVIOUS NEXT |