Decision Optimization

Originally posted by: david.rey

Hello,

I am having an "Infeasible or Unbounded" exception while solving a MIP with the CPLEX C++ API. The exception occurs during the execution of an application which calls CPLEX through a dynamic library (dll), I am working on Windows XP64. I attached a copy of the parameters and the model, when trying to solve this MIP on the interactive optimizer, it yields the same exception.

Could you help me identify what triggered this exception?

Thank you,
David Rey.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> david.rey wrote:
> Hello,
>
> I am having an "Infeasible or Unbounded" exception while solving a MIP with the CPLEX C++ API. The exception occurs during the execution of an application which calls CPLEX through a dynamic library (dll), I am working on Windows XP64. I attached a copy of the parameters and the model, when trying to solve this MIP on the interactive optimizer, it yields the same exception.
>
> Could you help me identify what triggered this exception?
>
> Thank you,
> David Rey.

Changing the time limit and threads count as in your .prm file is highly unlikely to have any influence on whether CPLEX declares a model infeasible during presolve. Indeed, if you just
run interactive CPLEX (12.3 I presume) with default settings, you get the same result.

Normally, when you get a declaration of infeasibility, you can get an explanation of the cause of
the infeasibility by running CPLEX's conflict refiner on the model. However, in this case, that
did not help, as the conflict refiner declares the model feasible. Combine this with the fact that
when you turn off CPLEX's presolve it finds a feasible solution with high accuracy, and I think the
issue here either involves some numerically unstable aspect of the model or an improper presolve
reduction.

I just ran CPLEX 12.4 on it, and it finds feasible solutions. I will investigate whether this change
involves a lucky change in path, or a legitimate correction of a problematic presolve reduction.

CPLEX 12.4 is not yet available through the academic initiative. Until it is, you can work around this by setting the presolve reduce parameter to 1 (primal reductions only). That avoids the
questionable declaration of infeasibility with hopefully limited impact on run time.

I will let you know as soon as I have more information.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

>
> I just ran CPLEX 12.4 on it, and it finds feasible solutions. I will investigate whether this change
> involves a lucky change in path, or a legitimate correction of a problematic presolve reduction.
>
> CPLEX 12.4 is not yet available through the academic initiative. Until it is, you can work around this by setting the presolve reduce parameter to 1 (primal reductions only). That avoids the
> questionable declaration of infeasibility with hopefully limited impact on run time.
>
> I will let you know as soon as I have more information.

I have verified that CPLEX 12.4 corrects the problem. In 12.4 we made a presolve fixing procedure stricter regarding the acceptable tolerances it used for fixing variables. The slightly looser tolerances in 12.3 permitted a variable fixing that introduced some round off error that subsequently
resulted in a declaration of infeasibility.

So, when 12.4 becomes available, this will be resolved with CPLEX's default settings. However,
after this investigation, while setting presolve reduce to 1 on this model instance resolves the
issue, it may not do so on other instances. So, for the short term, I recommend you turn presolve off instead. However, if this yields too much of a performance degradation, contact me directly at

klotz at us dot ibm dot com

and we can discuss other short term work arounds that should have less of a performance impact.
Ed
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: david.rey

I just ran my program with presolve turned off, it seems that the instance that triggered the exception was solved, but a few iterations later another instance triggered an "Infeasible or Unbounded" exception. I attached a copy of the last instance model and parameters.

Execution time for this set of parameters (which I set before launching my program) was not degraded, but I will now launch worst-case parameters with respect to running time to see if turning presolve off has any impact.

David Rey.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> david.rey wrote:
> I just ran my program with presolve turned off, it seems that the instance that triggered the exception was solved, but a few iterations later another instance triggered an "Infeasible or Unbounded" exception. I attached a copy of the last instance model and parameters.
>
> Execution time for this set of parameters (which I set before launching my program) was not degraded, but I will now launch worst-case parameters with respect to running time to see if turning presolve off has any impact.
>
> David Rey.

I had a look at the root node LP that prompted the declaration of infeasibility on this model with presolve off. The basis condition number was 1e+12. The model appears to be on the edge of
feasibility/infeasibility in the sense that it is legitimately infeasible with a feasibility tolerance
of 1e-9, but feasible with tolerances of 1e-8 or larger. With a condition number of 1e+12, you can
get infeasibilities on the order of 1e-6 that come from round off error. That appears to be the
case here, as the infeasibility was just barely above 1e-6:

CPLEX> r Reynodelp.sav
Warning: File contains basis. Basis is loaded.
Problem 'Reynodelp.sav' read.
Read time = 0.01 sec.
CPLEX> prim
Using devex.
Using devex.

Iteration log . . .
Iteration: 1 Infeasibility = 0.000005

Primal simplex - Infeasible: Infeasibility = 4.9703158009e-06
Solution time = 0.01 sec. Iterations = 1 (1)
Given this info, I suggest that for now you turn presolve off and set the feasibility and optimality
tolerances to 1e-5 instead of 1e-6.

For this model, CPLEX's presolve improves the numerical characterics via bound strengthening and coefficient reduction. So, the presolved model has better numerical characteristics. The unpresolved model doesn't have any major numerical issues, but it does have a few coefficients on
the order of 1e+6 and 1e+7. While basis condition numbers on the order of 1e+12 seem fairly
rare, condition numbers of 1e+8 and 1e+9 are more common. Those aren't really high, but combined
with those right hand side values of 1e+6 and 1e+7, there is potential for the slight infeasibilities
that we saw here.

Note that if you ever want to examine node LPs like this, you can do so by exporting them from a solve
callback function. This is already available in the diagnostic program at

http://www-01.ibm.com/support/docview.wss?uid=swg21400065
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: david.rey

Hi Ed,

First of all, thank you for your prompt replies. Sorry I was a bit in a hurry when I posted my thread yesterday, it missed some minor details.

I am currently using CPLEX 12.2 (Academic initiative), I guess a first step should be to upgrade to 12.3 (unless 12.4 will be shortly available ?). In my CPLEX code, I call CPLEX's conflict refiner (I don't know if that information appears in the prm/sav files), and as you found out, it does not provide any detected constraint-related conflict.

If I correctly understand your second reply, it's all about presolve. Can I then assume that there is no numerical instability in the model (I already work hard on that part)?

Regarding execution time, usually the MIPs are solved in less than 30sec, so even if turning presolve off has a moderate impact on performance it may still be ok for me. Ideally I would like to stick under 60sec, mainly because CPLEX is called up to 1500 times along the execution of my main program (although MIP instances sizes first increase form scratch and then decrease). I will lauch the program with presolve off to see if performance is degraded and I'll post a feedback as soon as I got results.

David Rey.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> david.rey wrote:
> Hi Ed,
>
> First of all, thank you for your prompt replies. Sorry I was a bit in a hurry when I posted my thread yesterday, it missed some minor details.
>
> I am currently using CPLEX 12.2 (Academic initiative), I guess a first step should be to upgrade to 12.3 (unless 12.4 will be shortly available ?).

I don't have a firm date, but I believe that 12.4 will be available shortly. I don't think moving
from 12.2 to 12.3 will help.

In my CPLEX code, I call CPLEX's conflict refiner (I don't know if that information appears in the prm/sav files), and as you found out, it does not provide any detected constraint-related conflict.
>
> If I correctly understand your second reply, it's all about presolve. Can I then assume that there is no numerical instability in the model (I already work hard on that part)?

I replied to your previous message, and there appears to be a little bit of numerical instability/
ill conditioning as described above. I don't see any serious problems when I look at the model.
But, somehow a few bases manage to have condition numbers of 1e+12. I did examine the
associated basis inverse and the solution values, but I was unable to use that to identify
particular aspect of the model that could be improved on.

>
> Regarding execution time, usually the MIPs are solved in less than 30sec, so even if turning presolve off has a moderate impact on performance it may still be ok for me. Ideally I would like to stick under 60sec, mainly because CPLEX is called up to 1500 times along the execution of my main program (although MIP instances sizes first increase form scratch and then decrease). I will lauch the program with presolve off to see if performance is degraded and I'll post a feedback as soon as I got results.
I recommend you do the following at for now.

1) Until the academic release of 12.4 is available, try running with presolve off and feasibility and
optimality tolerances of 1e-5.

2) If you run with those settings and see too much degradation in performance, post to this thread
again. If 12.4 is not available by the end of next week, contact me directly as I previously said,
and we'll discuss using an undocumented parameter that should address your original issue and enable
you to run your models with presolve on.

3) When 12.4 becomes available, download it immediately. At that point you should be able to get
consistent results without any non default parameter settings.

Ed
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: david.rey

Hi,

Executing my program with extreme parameters setting, produced significantly longer running times when presolve is turned off. In fact, when the instances sent to CPLEX increase in size along the program execution, optimality is almost never reached within the 1 minute time limit (although feasible solutions are found). I think in the long run I will need presolve, but I will try what you suggested (tuning feasibility tolerance) and see how performance is impacted.

I will be waiting for the 12.4 upgrade.

Thank you very much for all the tips.
David Rey.

PS: For info, I had set the thread parameter to 1 after experiencing "out of memory" exceptions. I am working on a quad-core machine but surprisingly, memory usage and performance improved a lot when somebody from the CPLEX team suggested I set the thread parameter to 1.
#CPLEXOptimizers
#DecisionOptimization