ILOG CPLEX 11.0 User's Manual > Infeasibility and Unboundedness > Managing Unboundedness > Diagnosing Unboundedness |
Diagnosing Unboundedness |
INDEX PREVIOUS NEXT |
You may be able to diagnose the cause of unboundedness by examining the output from the optimizer that detected the unboundedness. For example, if the presolve step at the beginning of optimization made a series of reductions and then stopped with a message like this:
Primal unbounded due to dual bounds, variable 'x1'.
it makes sense to look at your formulation, paying particular attention to variable x1
and its interactions. Perhaps x1
never intersects less-than-or-equal-to constraints with a positive coefficient (or, greater-than-or-equal-to constraints with a negative coefficient), and by inspection you can see that nothing prevents x1
from going to infinity.
Similarly, the primal simplex optimizer may terminate with a message like this:
Diverging variable = x2
In such a case, you should focus attention on x2
. (The dual simplex and barrier optmizers work differently than primal; they do not detect unboundedness in this way.) Unfortunately, the variable which is reported in one of these ways may or may not be a direct cause of the unboundedness, because of the many algebraic manipulations performed by the optimizer along the way.
An approach to diagnosis that is related to the technique discussed in Avoiding Unboundedness is to temporarily assign finite bounds to all variables. By solving the modified model and discovering which variables have solution values at these artificial bounds, you may be able to trace the cause through the constraints involving those variables.
Since an unbounded outcome means that an unbounded ray exists, one approach to diagnosis is to display this ray. In Concert Technology, use the method getRay
; in the Callable Library use the advanced routine CPXgetray
. The relationship of the variables in this ray may give you guidance as to the cause of unboundedness.
If you are familiar with LP theory, then you might consider transforming your model to the associated dual formulation. This transformation can be accomplished, for example, by writing out the model in DUA format and then reading it back in. (See the ILOG CPLEX Reference Manual for File Formats for a description of DUA as a file format.) The dual model of an unbounded model will be infeasible. And that means that you can use the conflict refiner to reduce the infeasible model to a minimal conflict. (See Diagnosing Infeasibility by Refining Conflicts for more about the conflict refiner.) It is possible that the smaller model will allow you to identify the source of the (dual) infeasibility more easily than the full model allows.
Copyright © 1987-2007 ILOG S.A. All rights reserved. Legal terms. | PREVIOUS NEXT |