Originally posted by: dbaena

Hello,

I have a MIP difficult problem. When I solve it with CPLEX 12.1 I obtain the following output:

Default variable names x1, x2 ... being created.   Default row names c1, c2 ... being created.   Tried aggregator 1 time.   MIP Presolve eliminated 0 rows and 15402 columns.   Reduced MIP has 36091 rows, 154186 columns, and 360760 nonzeros.   Reduced MIP has 7884 binaries, 0 generals, 0 SOSs, and 0 indicators.   Presolve time =    0.14 sec.   MIP emphasis: balance optimality and feasibility.   MIP search method: dynamic search.   Parallel mode: none, using 1 thread.   Root relaxation solution time =    2.44 sec.     Nodes                                         Cuts/    Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap     *     0+    0                       6.26212e+22                  45110     ---   0     0   1.06748e+17   714   6.26212e+22   1.06748e+17    45110  100.00%   *     0+    0                       1.15376e+17   1.06748e+17    45110    7.48%   0     0        cutoff         1.15376e+17                  70056    0.00%   Elapsed time =  27.04 sec. (tree size =  0.00 MB, solutions = 2)     Flow cuts applied:  871   Flow path cuts applied:  1   Gomory fractional cuts applied:  126

While with Cplex 12.4 I obtain the following output:

Default variable names x1, x2 ... being created.   Default row names c1, c2 ... being created.   Tried aggregator 1 time.   MIP Presolve eliminated 0 rows and 15402 columns.   Reduced MIP has 36091 rows, 154186 columns, and 360760 nonzeros.   Reduced MIP has 7884 binaries, 0 generals, 0 SOSs, and 0 indicators.   Probing time =    0.02 sec.   Tried aggregator 1 time.   Presolve time =    0.36 sec.   Found feasible solution after 0.68 sec.  Objective = 6.2618e+22   Probing time =    0.03 sec.   MIP emphasis: balance optimality and feasibility.   MIP search method: dynamic search.   Parallel mode: none, using 1 thread.   Root relaxation solution time =    2.40 sec.     Nodes                                         Cuts/    Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap     *     0+    0                       6.26177e+22                  45002     ---   0     0   1.06748e+17   714   6.26177e+22   1.06748e+17    45002  100.00%   0     0   1.13236e+17   700   6.26177e+22    Cuts: 2097    70824  100.00%   0     0   1.27550e+18   413   6.26177e+22    Cuts: 1167   296140  100.00%   0     0   1.27791e+18   331   6.26177e+22     Cuts: 858   303620  100.00%   0     0   1.27835e+18   284   6.26177e+22     Cuts: 497   309630  100.00%   0     0   1.27843e+18   272   6.26177e+22     Cuts: 285   312161  100.00%   0     0   1.27844e+18   247   6.26177e+22     Cuts: 182   312773  100.00%   0     0   1.27844e+18   237   6.26177e+22      Cuts: 74   312967  100.00%   0     0   1.27844e+18   251   6.26177e+22      Cuts: 42   313025 100.00%   0     0   1.27844e+18   250   6.26177e+22      Cuts: 22   313164  100.00%   *     0+    0                       1.28144e+18   1.27844e+18   313164    0.23%     Flow cuts applied:  1410   Mixed integer rounding cuts applied:  683   Flow path cuts applied:  8   Gomory fractional cuts applied:  91     Root node processing (before b&c):   Real time             =  105.13   Sequential b&c:   Real time             =    0.00   -------   Total (root+branch&cut) =  105.13 sec.

We can see an important difference in the objective function. In fact, CPLEX doesn't do a Branch And Cut because it stops at root node (adding cuts and maybe applying heuristics...).

On the other hand I have executed this problem with XPRESS and I obtain an upper bound of 5.15701e+17 and a lower bound of 4.98081e+17.
I think that CPLEX doesn't work well in this problem. I'm surprised because Cplex stop at root node with very low gap value. This is strange!

Can you help me?

Thanks a lot!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

What do the basis kappa numbers look like? I wonder if you have numerical stability issues.

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: dbaena

Thanks a lot Paul,

the information about Kappa for this problem is:

Max Kappa Value = 5.28229e+11
Percentage of numerically stable simplex bases = 0
Percentage of numerically unstable simplex bases = 0.871429
Kappa attention Value = 0.262714
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You do indeed have serious numerical stability problems. Given that, I would not put any faith in any of the results you got (including the bounds obtained from XPRESS). Your optimal value is definitely positive and probably rather larger, and that's about all we know.

You can try rerunning the model in both versions of CPLEX with the numerical emphasis parameter turned on. That will tell CPLEX to work extra hard to achieve numerical precision (at the cost of slower speed). You might also want to look at whether you can improve the numerical stability by rewriting the model. Any time I see numbers that large and the US national debt is not involved, I start thinking about poor scaling.

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: dbaena

Hi Paul,

thanks. Yes, I agree. I think I have a numerical issues. In order to solve it, I apply a scaling to the original problem (a/1e4 ; or a/1e5 or a/1e6). I hope get better results.

Thanks a lot!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

There's also a parameter for scaling you can put to "aggressive".

I don't think you are going to do scaling on your own that is going to do better than setting aggressive scaling and numerical precision. If that's not enough, you need to reformulate.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: dbaena

Thanks a lot for your answer!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Well, the automatic scaling of CPLEX is rather limited for (mixed) integer programs.
This is because CPLEX cannot scale integer variables (because this would change the semantics of the model), and it would also not scale the rows or continuous columns. It would only apply the scaling for the node LP relaxation solves.

For MIP models with poor numerical properties it is mainly the task of the modeler to think about what can be changed. For example, if some (integer) variable is expressing a dollar amount, and you are dealing with millions or billions of dollars, it is often useful to express the variable in millions of dollars (i.e., scale it by 1e-6) in order to reduce the matrix coefficients, bounds, and the numerical solution values for the variable that appear during the solving process. Also, in this case, the integrality condition can typically be ignored and the variable can be declared to be continuous. Or are you really looking at an individual dollar or cent if you are dealing with millions or billions?
Tobias
#CPLEXOptimizers
#DecisionOptimization