Originally posted by: MarioRuthmair

Hi!

Given is an IP model with additional user-defined cuts provided in a UserCutCallback. All CPLEX 12.3 parameters are default. All variables are first declared as IloNumVars with bounds 0,1 and later converted to ILOBOOL with IloConversion since in some cases only the LP relaxation should be obtained. The IloCplex object is created after the optional IloConversion.
For some instances of this model a strange problem arises: when the UserCutCallback is called in some branch-and-bound node and the LP solution values are obtained (with UserCutCallbackI::getValues), some of the variable values are negative (clearly outside the epsilon-interval, e.g. -0.38) and others may be much greater than 1, so clearly outside the feasible bounds 0,1.
The model is exported to a .lp-file before solving and here everything is ok: the variables are bounded correctly (0 <= var <= 1) and additionally included in the "Binaries" section.
Clearly, the cut separation makes problems when dealing with <0 or >1 values. Could anybody imagine what's the problem here?

Best regards, Mario
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Did you also export the model that has the IloConversions applied? Are the bounds still correct in that model?
If you encounter a value less than 0 or greater than 1 for a variable in the callback, what do the callback's getLB() and getUB() functions return for that variable?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MarioRuthmair

Yes, I exported the model after the IloConversions and the bounds are still correct and additionally all variables are in the "Binaries"-section of the lp-file.

I just checked getLB() and getUB() and if I notice e.g. a variable less than 0, the corresponding getLB() correctly returns 0 and getUB() returns 1.

If I disable presolving and probing for one of the failing instances the "less than 0"-problem does not arise. But since the problem arises only in about 1 percent of my test instances for the considered MIP model and the branch-and-cut possibly behaves completely different without presolving and probing, this may just be chance. But can it in principle have something to do with presolving or probing?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, presolving may causing trouble here. The callback in Concert operates on the original model formulation, not on the presolved one. So values for the presolved model have to transformed into values for the original model before the callback is invoked. If your model contains odd numbers then this transformation may introduce round off errors or other numerical troubles.
Could you export one of the instances for which you observe the problems to a SAV file (cplex.exportModel("model.sav")) and either post that here or send it to me: daniel(dot)junglas(at)de(dot)ibm(dot)com? I could then try to figure out what is going on.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MarioRuthmair

Here is a zipped model.sav of a problematic instance. I aborted optimization when I recognized variable values outside their bounds, and then exported the model. However, at least the lp-file does not contain the 1635 cuts added until then, so I'm not sure if the file is of use for you.
To say at least something about the structure of the added inequalities: a sum of binary variables (yl-variables in the file) with coefficient 1 is less or equal than 1.

What I further noticed when studying detailed CPLEX output (MIPDisplay=5, SimDisplay=1) was a kind of simplex degeneracy just before the wrong variable values are detected. Since the cuts are added deterministically the behaviour is reproducable. Here is a hopefully helpful shortened log:

... Iteration log . . . Iteration:     1   Dual objective     =           696.138249 Iteration:   212   Dual objective     =           696.220864 Iteration:   442   Dual objective     =           696.286783 Iteration:   655   Dual objective     =           696.333333 Perturbation started. Iteration:   809   Dual objective     =           696.333333 Iteration:  1028   Dual objective     =           696.460222 Iteration:  1252   Dual objective     =           696.576576 Removing perturbation. ... <16 cuts added in callback> Reinitializing dual norms . . . Computed 16 

new norms.   Iteration log . . . Iteration:     1   Dual objective     =           696.593750 Iteration:   216   Dual objective     =           696.689721 Iteration:   424   Dual objective     =           696.791531 Iteration:   633   Dual objective     =           696.917965 Iteration:   848   Dual objective     =           697.157095 Iteration:  1098   Dual objective     =           697.504470 Iteration:  1337   Dual objective     =           697.728128 Iteration:  1551   Dual objective     =           698.043241 Iteration:  1775   Dual objective     =           698.327752 Iteration:  2011   Dual objective     =           698.761905 Perturbation started. Iteration:  2202   Dual objective     =           699.000000 ... Iteration: 11732   Dual objective     =           722.777786 Markowitz threshold set to 0.1 Iteration: 11944   Dual objective     =           723.666674 Elapsed time =   50.53 sec. (12000 iterations). Iteration: 12145   Dual objective     =           723.777782 ... Iteration: 48175   Dual objective     =           739.809609 Repairing basis singularity. Added to superbasic list. Markowitz threshold set to 0.2 Iteration: 48220   Scaled dual infeas =            68.319373 Iteration: 48226   Dual objective     =           733.334436 ... Iteration: 51982   Dual objective     =           744.153979 Removing perturbation. Iteration: 51984   Dual objective     =           744.160000 ... Iteration: 52482   Dual objective     =           744.466665 Repairing basis singularity. Added to superbasic list. Markowitz threshold set to 0.3 Iteration: 52519   Scaled dual infeas = 47518664513537024.000000 Iteration: 52605   Scaled dual infeas =  836030228782.795288 Elapsed time =  425.85 sec. (53000 iterations). Iteration: 54011   Scaled dual infeas =       1791850.222266 Reperturbation started. Iteration: 54438   Scaled dual infeas =       3421990.739275 Iteration: 54784   Scaled dual infeas =       3284496.774933 Elapsed time =  442.46 sec. (55000 iterations). Iteration: 55583   Scaled dual infeas =       1534933.567751 ... Iteration: 198735 Scaled dual infeas =             0.371629 Iteration: 199040   Scaled dual infeas =             0.371585 Iteration: 199454   Scaled dual infeas =             0.371578 Iteration: 199819   Scaled dual infeas =             0.371577 Iteration: 200135   Scaled dual infeas =             0.000001 Iteration: 200402   Scaled dual infeas =             0.000001 Iteration: 200627   Scaled dual infeas =             0.000000 Iteration: 200875   Scaled dual infeas =             0.000000 Elapsed time = 1057.96 sec. (201000 iterations). Iteration: 201149   Dual objective     =       -106245.358142 Iteration: 201337   Dual objective     =        -72836.843117 Iteration: 201627   Dual objective     =        -63729.692440 ... Iteration: 694989   Dual objective     =           743.000237 Iteration: 695000   Dual objective     =           743.000237 Elapsed time = 4483.68 sec. (695000 iterations). Iteration: 695003   Dual objective     =           743.000235 Iteration: 695019   Dual objective     =           743.000236 Iteration: 695025   Dual objective     =           743.000236 Iteration: 695057   Dual objective     =           743.000236 Iteration: 695071   Dual objective     =           743.000238 Iteration: 695077   Dual objective     =           743.018755 Iteration: 695122   Dual objective     =           743.018756 Iteration: 695123   Dual objective     =           743.018756 Iteration: 695142   Dual objective     =           743.041901 Iteration: 695144   Dual objective     =           743.041901 Iteration: 695156   Dual objective     =           743.041899 Iteration: 695159   Dual objective     =           743.041900 Iteration: 695160   Dual objective     =           743.041900 Iteration: 695164   Dual objective     =           743.041900 Removing perturbation. ... <now the cut callback is called and the following variables are negative:> xl(14705) = -0.0416667, LB = 0, UB = 1 xl(15053) = -0.0416667, LB = 0, UB = 1 xl(15687) = -0.0833333, LB = 0, UB = 1 xl(16475) = -0.0833333, LB = 0, UB = 1 xl(16514) = -0.0833333, LB = 0, UB = 1 xl(16707) = -0.145833, LB = 0, UB = 1 xl(17025) = -0.0625, LB = 0, UB = 1 xl(17081) = -0.145833, LB = 0, UB = 1 xl(17177) = -0.0625, LB = 0, UB = 1 xl(17194) = -0.125, LB = 0, UB = 1 xl(17274) = -0.0416667, LB = 0, UB = 1 xl(17402) = -0.0416667, LB = 0, UB = 1 xl(17428) = -0.0833333, LB = 0, UB = 1 xl(17525) = -0.0833333, LB = 0, UB = 1 xl(17529) = -0.0833333, LB = 0, UB = 1 xl(17738) = -0.0833333, LB = 0, UB = 1 xl(17757) = -0.104167, LB = 0, UB = 1 xl(17761) = -0.145833, LB = 0, UB = 1 xl(17783) = -0.0416667, LB = 0, UB = 1 xl(18021) = -0.0833333, LB = 0, UB = 1 xl(18131) = -0.0416667, LB = 0, UB = 1 xl(18229) = -0.0833333, LB = 0, UB = 1 xl(18230) = -0.0833333, LB = 0, UB = 1 xl(18232) = -0.0833333, LB = 0, UB = 1 xl(18233) = -0.0833333, LB = 0, UB = 1 xl(18310) = -0.0625, LB = 0, UB = 1 xl(18311) = -0.0625, LB = 0, UB = 1 xl(18453) = -0.0416667, LB = 0, UB = 1 xl(18464) = -0.145833, LB = 0, UB = 1 xl(18658) = -0.0833333, LB = 0, UB = 1 xl(18659) = -0.0833333, LB = 0, UB = 1 xl(18741) = -0.145833, LB = 0, UB = 1 xl(18744) = -0.145833, LB = 0, UB = 1 xl(18858) = -0.0833333, LB = 0, UB = 1 xl(18889) = -0.104167, LB = 0, UB = 1 xl(18890) = -0.104167, LB = 0, UB = 1 xl(18912) = -0.0416667, LB = 0, UB = 1 xl(19088) = -0.145833, LB = 0, UB = 1 xl(19269) = -0.145833, LB = 0, UB = 1 xl(19270) = -0.145833, LB = 0, UB = 1 xl(19271) = -0.145833, LB = 0, UB = 1 xl(19273) = -0.145833, LB = 0, UB = 1 xl(19559) = -0.0416667, LB = 0, UB = 1 xl(19560) = -0.0416667, LB = 0, UB = 1 xl(19575) = -0.0833333, LB = 0, UB = 1 xl(19868) = -0.145833, LB = 0, UB = 1 xl(20102) = -0.0625, LB = 0, UB = 1 xl(20447) = -0.0833333, LB = 0, UB = 1 yl(3203) = -0.0833333, LB = 0, UB = 1 yl(3386) = -0.0833333, LB = 0, UB = 1 yl(3426) = -0.104167, LB = 0, UB = 1 yl(3459) = -0.0416667, LB = 0, UB = 1 yl(3519) = -0.0416667, LB = 0, UB = 1 yl(3559) = -0.0833333, LB = 0, UB = 1 yl(3565) = -0.0833333, LB = 0, UB = 1 yl(3575) = -0.145833, LB = 0, UB = 1 yl(3595) = -0.0833333, LB = 0, UB = 1 yl(3600) = -0.0625, LB = 0, UB = 1 yl(3635) = -0.145833, LB = 0, UB = 1 yl(3637) = -0.0833333, LB = 0, UB = 1 yl(3660) = -0.0833333, LB = 0, UB = 1 yl(3700) = -0.104167, LB = 0, UB = 1 yl(3745) = -0.145833, LB = 0, UB = 1 yl(3774) = -0.0625, LB = 0, UB = 1 yl(3819) = -0.0416667, LB = 0, UB = 1 yl(3820) = -0.0416667, LB = 0, UB = 1 yl(3846) = -0.145833, LB = 0, UB = 1 yl(3911) = -0.0625, LB = 0, UB = 1 yl(3922) = -0.104167, LB = 0, UB = 1 yl(3971) = -0.0833333, LB = 0, UB = 1 yl(4004) = -0.0833333, LB = 0, UB = 1 yl(4011) = -0.104167, LB = 0, UB = 1 yl(4044) = -0.145833, LB = 0, UB = 1 yl(4069) = -0.0833333, LB = 0, UB = 1 yl(4082) = -0.0625, LB = 0, UB = 1 yl(4116) = -0.145833, LB = 0, UB = 1 yl(4157) = -0.0625, LB = 0, UB = 1 yl(4182) = -0.104167, LB = 0, UB = 1 yl(4249) = -0.145833, LB = 0, UB = 1 yl(4310) = -0.145833, LB = 0, UB = 1 ...

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

I found set both root lpmethod and subprob's lpmethod to network simplex can resolve the degeneracy issue.

Could you please try?

John Cui
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MarioRuthmair

I tried network simplex for computing LP relaxations and indeed it solved this instance without degeneracy issues. However, it took about 8600 sec. to solve it compared to about 2400 sec. when using CPLEX auto settings for simplex but disabling presolving and probing.
But still these are just ways to overcome the problems for this single instance. The network simplex may suffer from degeneracy on other instances and disabling presolving and probing may not help as well all the time.
I know that simplex degeneracy cannot be avoided completely but if there would be a way to at least avoid variable values outside their defined bounds (with epsilon tolerance) I would be lucky. More precisely, in the example above I don't understand why simplex stops here when the LP solution still is not feasible for this model. Would it be a general idea to emphasize numerical stability or to lower parameter EpOpt?
Besides, is EpOpt the correct epsilon here?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I ran your SAV file and accumulated kappa statistics, as follows:

Branch-and-cut subproblem optimization:
Max condition number: 3.4977e+13
Percentage (number) of stable bases: 90.11% (1111)
Percentage (number) of suspicious bases: 8.27% (102)
Percentage (number) of unstable bases: 1.62% (20)
Percentage (number) of ill-posed bases: 0.00% (0)
Attention level: 0.005693
CPLEX encountered numerical difficulties while solving this model.

Note that the worst basis condition number had magnitude 10^13, and that 20 unstable bases were encountered. This is without your added cuts, but I suspect you get the same or worse conditioning with the cuts. I think that ill-conditioning could account for, or at least contribute to, apparent infeasibility when CPLEX backs out from a solution to the internal (presolved) model to a solution to the original model.

Bad scaling of model coefficients is usually the first possible cause of ill-conditioning that I check, but your model seems to be pretty well scaled. So it's possibly something in the structure of your constraints (but don't ask me what). A really blind guess here is that you might look for expressions in your model that get used repeatedly. I noticed some recurrences in the connectxl constraints, for example. Assigning repeated expressions to new variables and then substituting the new variables might possibly help the conditioning. At least I think I've seen it help once or twice.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MarioRuthmair

Hi Paul,

thanks for your detailed analysis of my model and your suggestions how to deal with it.
I will revise my model constraints, maybe I can find a numerically more stable variant.

One more question, how did you get those kappa statistics? Can I possibly analyze the stability of my models myself in further problematic cases?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

In the interactive optimizer, there is a parameter (might be under"set mip strategies") whose name begins with"kappa". It determines how (and if) kappa stats will be recorded. Set that, optimize the model, then look under"display solution"for the command to display the basis stats.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MarioRuthmair

Many thanks for all your hints, Paul.
#CPLEXOptimizers
#DecisionOptimization