Topic
4 replies Latest Post - ‏2013-05-06T07:31:24Z by DanielJunglas
CplexUser1453
CplexUser1453
24 Posts
ACCEPTED ANSWER

Pinned topic model implementation : order of constraints

‏2013-04-25T18:23:04Z |

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

 

  • CplexUser1453
    CplexUser1453
    24 Posts
    ACCEPTED ANSWER

    Re: model implementation : order of constraints

    ‏2013-04-29T07:44:51Z  in response to 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.

  • DanielJunglas
    DanielJunglas
    22 Posts
    ACCEPTED ANSWER

    Re: model implementation : order of constraints

    ‏2013-04-29T11:16:43Z  in response to CplexUser1453

    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.

     

    • CplexUser1453
      CplexUser1453
      24 Posts
      ACCEPTED ANSWER

      Re: model implementation : order of constraints

      ‏2013-04-29T12:39:23Z  in response to DanielJunglas

      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.

      • DanielJunglas
        DanielJunglas
        22 Posts
        ACCEPTED ANSWER

        Re: model implementation : order of constraints

        ‏2013-05-06T07:31:24Z  in response to CplexUser1453

        > 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.