Originally posted by: CplexUser1453

Hello

I have stumbled upon a PhD. thesis claiming that the order in which constraints are implemented influences CPLEX performance (for CPLEX 11.00 at least) :

"From observations, the best results are obtained from Cplex when the following are sati ed:
1. Each constraint is fully iterated before the next is considered.
2. The variables are entered into the constraints in the same order that they appear
in the objective function.
3. Dominant coecients for the variables are positioned before smaller coecients
of the same variable in the objective function" (paragraph 4.3.2)

http://wiki.ms.unimelb.edu.au/tiki-download_file.php?fileId=762

I did play a little bit with my own production planning model and it seems that my CPLEX 12.4 does behave slightly differently depending on the order of constraints in the model. I did not find much on this topic anywhere else so here are my questions :

1) Was this really an issue in CPLEX 11.0 and could it still have an impact on CPLEX 12.4?

2) If the answer is yes, are recommendations above still valid for CPLEX 12.4? Are there any other good practices regarding the order in which constraints are implemented?

Thanks a lot

Originally posted by: CplexUser1453

It's only now that I realized that I may have posted my question in the wrong forum, it is not really an OPL issue but rather a CPLEX issue, so I guess it should be in Mathematical Programming >‎ CPLEX Optimizer. Sorry for that and I will be glad if the forum administrator could correct my mistake.

Yes, the order in which variables and constraints are presented to the solver can indeed matter, in particular for MIP. This is one aspect of "performance variability".

This can be easily seen by looking at a (hypothetical) heuristic that loops over the variables and sets each variable to 1 until all constraints are satisfied. Depending on the order of the variables such a simple heuristic may find the optimal solution or may not find a feasible solution at all.

The effect of reordering variables and/or constraints is highly dependent on problem type and instance. Hence there are no general guidelines. In fact, it is hard to tell whether the performance variation you observe by reordering problem data is due to the reordering or just random noise.

Originally posted by: CplexUser1453

Thanks a lot for your response.

Well, normally with the determninistic b&b option I should be able to avoid the noise factor, right?

It seems also that my question may be about what exactly CPLEX is doing in presolve and I understand if you don't want respond to that in a public forum.

In any case, if the only thing that you can suggest is that I should try different ordering and test on a large number of instances then that's what I will do.

> Well, normally with the determninistic b&b option I should be able
> to avoid the noise factor, right?
>
Only part of it. "deterministic" here only means that for the exact same input CPLEX will produce the same search path. If you change the order of constraints then search paths may be quite different.

> It seems also that my question may be about what exactly CPLEX is doing in presolve
> and I understand if you don't want respond to that in a public forum.
>
This is not limited to presolve. The order in which variables and constraints are presented to CPLEX basically influences all components of CPLEX.

> In any case, if the only thing that you can suggest is that I should try different ordering
> and test on a large number of instances then that's what I will do.
>
Hm, actually I would suggest to not spend any time on trying to order constraints in an "optimal" way. As I said, you may end up tuning random effects here.