Originally posted by: hllsen

Hello,

I solve an LP iteratively by adding cuts (Benders) using Cplex 12.7.0 callable library. To get the most out of the re-optimization features, I use the same cpxenv and cpxlp, and add the generated cuts to the lp and re-optimize. With some instances, CPXlpopt finds the model unbounded but the LP is bounded (in which all variables are bounded from below and above). However, when I write out this model (either as lp or sav), the interactive optimizer quickly finds the optimal (even with the sav file which includes the basis that supposed to lead to the unboundedness). I thought this might be because of a numerical difficulty and tested with numerical emphasis on but nothing changed (the condition number of the basis is not huge, 1e+4).

I am guessing, there are some internal parameters which are modified by cplex during the optimization process (for example, Markowitz threshold is one of them) and they are kept at those values after solution process has ended. Then, when a new constraint is added and the model is re-optimized these modified parameters lead to incorrect result. Does this make sense? If so, is there a way to prevent it without resorting to using a new environment for each LP? Or is there a way to print/reset these internally modified parameters?
Thank you,
h.

PS: I couldn't attach the lp file due to size limit. Let me know if you need it.

Edit: Forget to attach the other files. Need to write this note to pass the spam prevention algorithm.

Sorry, I could not reproduce the issue here. I did the following with the 12.7.0 interactive optimizer:

CPLEX> read curprob.sav
CPLEX> read curparams.prm
CPLEX> opt

I also tried to use 'tranopt' (dual simplex) and 'primopt' (primal simplex) instead of just plain 'opt'. I even tried with 'set advance 0' (to drop the basis from the SAV file). In all cases CPLEX came up with an optimal solution and no claim of unboundedness.

Can you please double check whether you attached the right problem?

Originally posted by: hllsen

Hello Daniel. When the model is solved in a fresh cplex environment (like interactive optimizer), the issue does not happen. Unfortunately, it is somewhat hard to reproduce and only happens when this LP is created iteratively by adding cuts and re-optimized along the way inside the same environment. That is, first, the LP is solved without the cuts (cuts are named as BeC_*_*__ in the lp file) then oracle generates the first 300 cuts (BeC_1_*__ to BeC_300_*__) which are added to the model and CPXlpopt is called again. This process goes for 2 more iterations (i.e., the group of cuts BeC_301_*___ to BeC_600_*___   and   BeC_601_*___ to BeC_876_*___ are added to the model and reoptimized) and after that CPXlpopt returns unbounded (even though interactive optimizer does find an optimal solution). That is why I thought that this issue is related to the parameters cplex internally modify. If I can find which parameter is the culprit, I can reset that parameter to its default vaule. I tried reseting Markowitz threshold in between iterations with no avail.

Thank you for the file and the explanation. With that I managed to reproduce the problem here. We are looking into that now.

Originally posted by: hllsen

I am glad that it helped. Thanks for the notification. I will be looking forward to hear your conclusion.

Originally posted by: BoJensen

I took a look at this issue. Your problem data has some very large matrix coefficients (when the solution is unbounded) :

CPLEX> display prob stat
Problem name         : prob3.sav
Objective sense      : Minimize
Variables            :  451800  [Box: 451800]
Objective nonzeros   :    1800
Linear constraints   :    2655  [Less: 1500,  Greater: 1155]
  Nonzeros           : 1296107
  RHS nonzeros       :    1155
Variables            : Min LB: 0.000000         Max UB: 100.0000      
Objective nonzeros   : Min   : 1.941648         Max   : 9383.618      
Linear constraints   :
  Nonzeros           : Min   : 1.000000         Max   : 4.469029e+09  
  RHS nonzeros       : Min   : 1.000000         Max   : 2.224015e+07

Even the problem has only boxed variables, it's still possible to incorrectly declare the problem unbounded. This can happen when a slack is used as entering variable and bad numerics make the dual solution inaccurate.

I suggest to increase the optimality tolerance :

CPXXsetdblparam(env, CPX_PARAM_EPOPT, 1.0e-5)

Let me know if this doesn't fix your problem.

Originally posted by: BoJensen

Rescaling the cuts you add, might also fix it.
 

Originally posted by: hllsen

Before (the dual values coming from the oracle were directly used in the cut and) it was worse, in this version (which leads to unboundedness issue) the cuts are scaled so that the minimum cut coefficient is always 1.0 (unless it makes the maximum cut coefficient too big). Do you have any suggestion on how to achieve a better scaling?

Originally posted by: BoJensen

I took a look at the cuts and I agree those will not be possible to improve by a row scaling. I also tracked a particular variable through the different cuts and it seemed it's cut coefficient increases over time i.e first cuts are OK, then the coefficients increase.

Originally posted by: hllsen

That's possible, I didn't think about observing the evolution of a cut coefficient. Nevertheless, it is somewhat out of my control since the coefficients are coming from the oracle.

Originally posted by: hllsen

Thanks for the suggestion BoJensen. It turns out Cplex finds the optimal for this problem (within the iterative scheme) with 1e-5 but not 1e-6.  However, I have no direct control to this parameter, it depends on the overall tolerance asked by the user. Also, this parameter does not really explain why Cplex returns unbounded for the very last model when it is solved  within the iterative setting but not in a fresh cplex environment (even if it is started with the basis for which the iterative version declares unbounded).

Originally posted by: BoJensen

The main problem is that the model has both small and very large matrix coefficients. Having a matrix coefficients spread in the order of 1.0e+9 carries the risk of creating numerical instability. If a variable with a 1.0e+9 matrix coefficient enters the basis, then all calculations IN CPLEX will be dependent on a LU factorization with this high number. Inaccuracy in calculations is hard to avoid in such a case, since finite precision is used.

You observe starting with the previous found basis cause trouble and solving from a clean start solves fine. But there is no guarantee that this will hold true, the reverse could also happen. I suggest looking into improving the model formulation, this will ensure you get a stable solve/application.
 

Originally posted by: hllsen

Actually, what I observe is not exactly "starting with the previous found basis cause trouble and solving from a clean start solves fine". Even if I start from that basis in the interactive optimizer, cplex solves the problem. But, if I do this inside the same cplex environment in callable library, then cplex returns unbounded. I assume if I create a new "clean" cplex environment in callablelibrary and supply the offending model with its basis, then it will be solved again. Therefore, I think that (even though there are numerical issues with the model) the root of the issue is that the parameters are modified inside the cplex environment during a solve and not reseted for re-optimization.

Originally posted by: BoJensen

Unfortunately it's not a 1:1 by comparing reading in the solution into the interactive and solving problems in sequence by using the callable library. They might take different paths. I suggest to fix the numerical issues in the model to get a stable run or as a temporary fix increase optimality tolerance as previously suggested.
 

Originally posted by: hllsen

I suspected that was the case. Thanks for the suggestions. Unfortunately, I cannot directly control the evolution of the model (to fix the numerical issues) because the cuts comes from dual solutions. Since I am not dealing with a specific type problem or an instance (but rather, developing a generic decomposition solver), a temporary fix is not viable either.

Nevertheless, I created a new lp in a new cplex environment at the point where the previous one returns unbounded and copy the lp model into the new environment. This new environment finds an optimal solution as well. Since I couldn't find a better way, I did this operation with CPXwriteprob and CPXreadcopyprob. Is there a better way of achieving this result (i.e., resetting the internal cplex data/parameters)?

Originally posted by: BoJensen

As said the problem lies in the numerics of the data, it may be that it will work by creating a new environment/model, but I consider this to be sort of "luck". It's unfortunate you can not correct the model, which would be the best thing to do (or increase opt tolerance as suggested). If it works with CPXwriteprob and CPXreadcopyprob, then stick with this, though I believe this new solve could result in unbounded too.

Originally posted by: hllsen

Thanks for your patience BoJensen. I managed to modify the cut scaling routine and circumvent the situation. By the way, you are right about the model -- i.e., oracle should return more stable cut coefficients and there are ways to achieve this. I already implemented such methods and they work. This unboundedness issue was happening with a pure oracle -- i.e., when such options are switched off -- and since I wanted to fix this parameter setting I didn't want to modify the oracle. Thanks again.