Originally posted by: SystemAdmin

Hello Group,

I have two models that are exactly identical in terms of number of variables and constraints. Even the names on the variable and constraints are identical. They both are only different in patches in the order in which the variables or constraints are created.

For example, one model might have:

X1 + X2 <= 10
X3 + X4 <= 15

And another might have:

X3 + X4 <= 15
X1 + X2 <= 10

The file sizes of both the model's LP files are exactly the same. Solving the model results in the exact same objective function. I have encountered cases where the order in which the variables are created might result in different optima, if multiple optima exists for that model. But in this situation I am seeing very different solve times, as follows:

Model 1: Solution time = 159.84 sec. Iterations = 2215027 Nodes = 133069 (10289)
Model 2: Solution time = 248.18 sec. Iterations = 3890735 Nodes = 207838 (13981)

What's interesting is that I am getting similar run times in CPLEX 9.1. I am attaching you 4 log files, 2 each for CPLEX 12.1 and CPLEX 9.1. I didn't have both versions of CPLEX installed in the same machine so the run times are not comparable between the two sets.

Only new parameter setting for all the four runs are 'set mip cuts all 2'

Could you pls let me know what could cause this difference in CPLEX 12.1 run times and how this could be addressed effectively?

Thanks in advance,
Vivek.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You are facing a problem that we call "performance variability". As you know, MIP (and MIQP, which you are facing) is an NP hard problem. For this reason, the search space can be exponentially large. The reason why CPLEX can still solve many problems that are intractable in theory is because clever decisions are made during the search that often enable CPLEX to discard the majority of the potential search tree nodes without even looking at them. One important way of improving the average solving speed of a solver is to modify the heuristic algorithms to take those search decisions in such a way that they get "lucky" more often.

The order of the variables and constraints plays a role in the decision making process of the search algorithm, namely as a tie-breaker if two variables or constraints look identical in all other measures that are applied. Thus, if you have two identical models that only differ in the order of the variables and/or constraints, you will see different decisions during the search process, and consequently different search trees and different solving times. And due to the NP-hardness of MIP, one tiny difference for example in a branching decision at the top of the tree can have a huge impact on the size of the resulting search tree.

This said, if you compare two solvers, two versions, or two parameter settings, it is just not possible to assess the quality of the two alternatives by looking at a single model. Performance variability is introducing so much random noise that this cannot be considered to be a sound statistical experiment. In order to compare two alternatives, you need to run many more problem instances to get a result that can be called statistically significant.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks Tobias!

I agree that we just can't go by one single experiment for solve times between different versions. We did try out couple other models and thought CPLEX 9.1 performed better. Are there any differences in the default behavior in CPLEX 12.1 compared to 9.1?

You mentioned about the heuristics. Could you pls let me know which heuristics I can try out?

Thanks,
Vivek.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

There are of course lots of changes between CPLEX 9.1 and 12.1. Most of the time, models get faster due to our algorithmic progress. But in rare cases, a new version is actually slower than the old one. Often one can recover the speed by using non-default parameter settings.

Which parameters to try is hard to tell. For a first shot, just try the tuning tool that comes with CPLEX 12.1. Maybe it spits out a parameter combination that suits your need.

If possible (i.e., you are allowed and willing to), could you send me your models by email to achterberg at de dot ibm dot com? Then I could take a look at them and see if I find some improvements.

Tobias
#CPLEXOptimizers
#DecisionOptimization