Decision Optimization

Expand all | Collapse all

please help for MIP model running long time

  • 1.  please help for MIP model running long time

    Posted 29 days ago
      |   view attached
    Dear everyone,

    I am using CPLEX 12.8 on a PC with RAM 64GB.  But the model is running for a long time (15 hours) and doesn't get results.  Although I used "set mip strategy startalgorithm" with a number between 1 and 5, the model still works for such a long time.  

    Could you look at the attached log, and help me? I am really grateful.

    Best regards,
    Nguyen






    ------------------------------
    Ken Nguyen
    ------------------------------

    Attachment(s)

    txt
    log.txt   24K 1 version


  • 2.  RE: please help for MIP model running long time

    Posted 29 days ago
    1. You chose "set mip strategy startalgorithm 4". That is Barrier + Crossover.  Did you try other algorithms as well?   The default is to run concurrent opt, which means that CPLEX will run Dual simplex, Primal Simplex and Barrier+Crossover.  But if the issue is that Crossover takes a very long time (as seems to be the case), then you may want to switch to another algorithm instead.

    2.  Was CPLEX still printing log lines regularly when you stopped it, or did it stop to print any log line for a long time before you copied the log?  During the last part of the log (from 'Dual crossover'), CPLEX actually runs two crossover algorithms concurrently (Primal and Dual).  But it can only print the log for one, in this case Dual.  Knowing whether Dual was stopped or not may indicate which of the two is slower.

    3. Is there a specific reason why you didn't try the latest version available on https://ibm.biz/CPLEXonAI?  Version 12.8 is already 3 years old, and version 12.10 is available since last December.

    ------------------------------
    Xavier
    ------------------------------



  • 3.  RE: please help for MIP model running long time

    Posted 29 days ago
    Edited by Ken Nguyen 27 days ago
    Hi Xavier,

    1. "set mip strategy startalgorithm of 4" is the fastest compared with other algorithms. I tried with small data example and get results about 3 minutes. The log for this example can see  "log_smalldata" attached.

    2. But when run with big data with using "set mip strategy startalgorithm of 4" , the model does not stop for a long time (over 25 hours), so I copy lines into a file "log_bigdata".

    No, it is stuck at the log line for a long time. So, could you help me with how to get results for the big data case for a few hours?

    Thank you,

    Best regards,
    Ken Nguyen














    ------------------------------
    Ken Nguyen
    ------------------------------

    Attachment(s)

    txt
    log_smalldata.txt   9K 1 version
    txt
    log_bigdata.txt   62K 1 version


  • 4.  RE: please help for MIP model running long time

    Posted 27 days ago
    Edited by Ken Nguyen 27 days ago
      |   view attached
    Hi Xavier,

    Please find the new copied the log, the model is running over 24 hours. Could you help me to get results?

    Best regards,
    Ken Nguyen


    ------------------------------
    Ken Nguyen
    ------------------------------

    Attachment(s)

    txt
    log_bigdata_new.txt   402K 1 version


  • 5.  RE: please help for MIP model running long time

    Posted 24 days ago
    From the logs you sent, it appears your problem is mostly a LP, and time is spent on the first linear relaxation.
    A common cause for poor LP performance is ill-conditioning.
    To rule out such numerical issues, I suggest you do the following actions, under Cplex interactive:

    - once the problem is read by cplex interactive, run `display problem stats`: this command will compute the lowest and highest magnitudes
    of coefficients; if the ratio between highest and lowest is too high, this indicates numerical issues.
    - before running solve in cplex interactive, set the `read datacheck` parameter to 2. This value will  perform detailed checks on numerical issues,
    see https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/progr_consid/modelingAssistance/introModelingAssistance.html
    for details.

    To summarize, here's the augmented script to run in cplex interactive to check for numerical issues:

    > read ...
    > display problem stats
    > set read datacheck 2
    > opt

    If your problem suffers from numerical issues, this should show up as warnings in the output.


                Philippe.

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



  • 6.  RE: please help for MIP model running long time

    Posted 24 days ago
    Dear Philippe,

    Thank you,

    How to run `display problem stats` in CPLEX?

    Best regards,

    Ken Nguyen


    ------------------------------
    Ken Nguyen
    ------------------------------



  • 7.  RE: please help for MIP model running long time

    Posted 24 days ago
    Commands should be run from the "cplex.exe" interactive optimizer.
    This executable is located in the COS installation at: <cos_root>/cplex/bin/x64_win64/cplex.exe.
    A full description of the interactive optimizer can be found here:
    https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cplex.help/CPLEX/homepages/interactiveoptimizercommands.html

    Note that when serializing the model, you should use SAV format to avoid numerical roundoffs.

    The script I suggest is then the following:

    > read  myproblem.sav <------------ path where your SAV file is.
    > display problem stats
    > set read datacheck 2
    > opt

    Data analysis is performed before solve, so you might as well set a time limit of 1 to perform the analysis and stop after.
    The output of this script should help use detect (or rule out) numerical stability issues.


            Philippe.




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



  • 8.  RE: please help for MIP model running long time

    Posted 24 days ago
      |   view attached
    Dear Philippe,

    Could you see the file attached and tell me to know, where are numerical stability issues?

    Thank you,

    Best regards,
    Ken Nguyen


    ------------------------------
    Ken Nguyen
    ------------------------------

    Attachment(s)

    docx
    checking.docx   14K 1 version


  • 9.  RE: please help for MIP model running long time

    Posted 23 days ago
    Your model has numerous numerical issues, which are likely to impact its run performance, and are certyain
    to result in poor quality of the solution

    The first issue I see is many big-M formulations with 1e+7 coefficients.
    This is known to introduce numerical instability, and you should prefer indicator constraints instead.
    Cplex manages the association between binary variable and constraint internally, without instabilities.

    See this article for more details:

    https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/discr_optim/indicator_constr/04_Interactive.html


    I also see coefficients in constraints with a ratio of 1e+16, this is too much. The range of orders of magnitudes should not exceed 1e+6, in other
    terms, the ratio of the biggest coefficient (in absolute value) should not exceed 1e+6, otherwise you will encounter numerical instabilities.
    A ratio of 1e+16 is definitely too large, and should be fixed.

    There are other issues, but these two topics seem to me the highest priority to fix.


         Philippe.

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



  • 10.  RE: please help for MIP model running long time

    Posted 23 days ago
    Dear Philippe,

    That means that I need to fix Big_M coefficients that are less than 1e+6 to get the result in rich quality. Right?

    Best regards,
    Ken Nguyen


    ------------------------------
    Ken Nguyen
    ------------------------------



  • 11.  RE: please help for MIP model running long time

    Posted 23 days ago
    Not exactly. I see two action items:

    1. substitute  big-M formulations on binary variables with indicator constraints, wherever possible.
    2. investigate why some linear constraints have such a huge range of coefficients (1e+16): this should definitely be modeled in a different manner.


          Philippe.

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



  • 12.  RE: please help for MIP model running long time

    Posted 21 days ago
    Edited by Ken Nguyen 21 days ago
    Dear Philippe,

    I have a constraint with Big_M as below.  Could you help me transfer it to an indicator constraint in CPLEX?

    Best regards,
    Ken Nguyen


    ------------------------------
    Ken Nguyen
    ------------------------------



  • 13.  RE: please help for MIP model running long time

    Posted 19 days ago
    In the above formulation, the sum of Z variables is always smaller than capacity "c", but equal to zero if binary variables X equals 0.

    I would model this by using two constraints:

    - one plain linear constraint: sum(Zs) <= c
    - one _indicator_ constraint, stating that sum(Zs) is zero when X is zero. To express this in DOcplex, use Model.add_indicator,
    which takes three arguments:

    - a binary variable (here X)
    - a linear constraint, whose truth value will be controlled by X, here it is sum(Zs) ==0
    - a value(0 or 1) which triggers the action between the binary variable and the linear constraint: default is 1 but in your case it's 0: the sum of Zs variables becomes equal to zero when X is 0.

    Here is a very simple example code to illustrate this:

    def model_with_indicators():
       m = Model()
       zs = m.continuous_var_list(3, name='Z')
       x = m.binary_var(name='X')
       # this comnstraint is NOT posted
       all_zeros = m.sum(zs) == 0
       m.add_indicator(x, all_zeros, active_value=0, name="my_indicator")
       m.add(m.sum(zs) <= 10)  # capacity
       m.maximize(m.sum(zs))
       # force x to 0 to see what happens

       x.ub= 0
       return m

    Solving this model yields all Zs to 0, because X ==0 forces the linear constraint "sum(zs) ==0" to be satisfied.

    Note that
    - the "sum(zs)==0" should NOT be added to the model, as its truth value is not certain: it depends on the value of X
    - we had to specify "active_value=0" as the triggering value (default is 1)
    - no more big-M value is used, which result in a much safer model.

    Here is an extract of the DOcplex documentation for `Model.add_indicator`

    def add_indicator(self, binary_var, linear_ct, active_value=1, name=None):
    """ Adds a new indicator constraint to the model.

    An indicator constraint links (one-way) the value of a binary variable to
    the satisfaction of a linear constraint.
    If the binary variable equals the active value, then the constraint is satisfied, but
    otherwise the constraint may or may not be satisfied.



        Let me know if you have questions.

                     Philippe.



    ​​

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



  • 14.  RE: please help for MIP model running long time

    Posted 19 days ago
    Dear Philippe,

    In line "m.add(m.sum(zs) <= 10)  # capacity".  That means the capacity "c" is 10 intead of 999999999. Right?.

    I tried running this example into CPLEX, but it is an error, could you help me, how to use this example?
    Best regards,
    Ken Nguyen


    ------------------------------
    Ken Nguyen
    ------------------------------



  • 15.  RE: please help for MIP model running long time

    Posted 19 days ago
    Yes, capacity is 10, real capacity, no bigM is required with indicators.
    As for errors, I can't see the text of errors, but I can't see the import, of course you should import Model class (which I did not include, my bad)
    add one line before the code.

    from docplex.mp.model import Model

    If you still have errors, post the text of errors you get.

       Regards

                       Philippe.


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



  • 16.  RE: please help for MIP model running long time

    Posted 19 days ago
    Hi Ken,

    do you use OPL or docplex (the python CPLEX API) ? 
    Philippe assumed docplex.

    If you use OPL

    - one plain linear constraint: sum(Zs) <= c
    - one _indicator_ constraint, stating that sum(Zs) is zero when X is zero.

    can be written

    range s=1..10;

    int c=4;

    dvar boolean z[s];
    dvar boolean x;

    subject to
    {
    (sum(i in s)z[i])<=c;
    (x==0)=>(0==(sum(i in s)z[i]));
    }


    ------------------------------
    ALEX FLEISCHER
    ------------------------------



  • 17.  RE: please help for MIP model running long time

    Posted 19 days ago
    Hi ALEX,

    I use OPL.

    But if the capacity "c" is over 100,000,000. Please ask that how to determine suitble  "c" for the linear constraint: sum(Zs) <= c?

    Best regards,
    Ken Nguyen


    ------------------------------
    Ken Nguyen
    ------------------------------



  • 18.  RE: please help for MIP model running long time

    Posted 15 days ago
    Hi ALEX,

    Please help me.

    I use OPL. 


    But if the capacity "c" is over 100,000,000. Please ask that how to determine suitble  "c" for the linear constraint: sum(Zs) <= c?

    Best regards,
    Ken Nguyen


    ------------------------------
    Ken Nguyen
    ------------------------------

    ------------------------------
    Ken Nguyen
    ------------------------------