Decision Optimization

 View Only
  • 1.  Order of constraints

    Posted Wed March 24, 2021 02:53 PM

    Hello,

    I noticed that the order of constraints of a MILP can have an impact on the solution quality of the same instance under the same solution time limit. I have a couple of questions regarding this:

    1. Are there any settings or MIP parameters to help this issue?
    2. Would it be helpful to group constraints that have common decision variables?
    3. Could a consistently better ordering be found? Is it worth spending time?
    4. Do you have a general suggestion?

    Thank you in advance.

    Kind regards,

    Begun



    ------------------------------
    Begun Efeoglu
    ------------------------------

    #DecisionOptimization


  • 2.  RE: Order of constraints

    Posted Wed March 24, 2021 03:24 PM
    Hi

    1. Are there any settings or MIP parameters to help this issue?

    ==> You may run CPLEX with different random seeds to do some measures. You may change the priority of a decision variable to tell CPLEX whether branch early or not.
    "A priority order assigns a branching priority to some or all of the integer variables in a model."

    2. Would it be helpful to group constraints that have common decision variables?

    ==> Sometimes yes and it s good to branch first on subset1 and then on subset2. This depends on the model and impact should be checked with many random seeds

    3. Could a consistently better ordering be found? Is it worth spending time?

    ==> Sometimes yes

    4. Do you have a general suggestion?

    ==> You may try to read https://www.ibm.com/support/pages/cplex-performance-tuning-mixed-integer-programs

    or http://www.optimizationdirect.com/ODheuristics.php

    regards

    Many links in https://www.linkedin.com/pulse/low-barrier-entry-optimization-through-cplex-alex-fleischer/

    ------------------------------
    [Alex] [Fleischer]
    [EMEA CPLEX Optimization Technical Sales]
    [IBM]
    ------------------------------



  • 3.  RE: Order of constraints

    Posted Wed March 31, 2021 04:30 AM
    Hello,

    The order of constraints has an impact on the MIP search. However, there is no algorithm to reorder constraints to ensure
    a better performance. If your MIP is slow, I suggest you try tuning parameters, starting with`mip emphasis`, see
    https://www.ibm.com/support/knowledgecenter/SSSA5P_20.1.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/MIPEmphasis.html
    for details.
    If you are using a time limit, cplex 20.1 introduces a new mip emphasis value 5 to get better solutions faster (however, proof of optimality may take longer..)
    If not using 20.1 try values 2,3,4.

    In addition, one way to measure the variability of MIP performance is to load your model in cplex.exe interactive optimizer and do
    a `tool runseeds 50`: if runs differ widely, it may mean your data has numerical issues.
    To check that, add the following option in interactive (or through APIs)

    `set read datacheck 2`
    (see https://www.ibm.com/support/knowledgecenter/SSSA5P_20.1.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/DataCheck.html)

    This helps diagnosing numerical problems

        Hope this helps


            Philippe.

    ------------------------------
    Philippe Couronne
    ------------------------------