Decision Optimization

 View Only

  • 1.  How do we control kappa number from increasing, how to trace what numbers cause kappa increase?

    Posted Wed December 08, 2021 09:23 AM
    Hi Experts
    We are solving a bunch of pure LP problems sequentially with CPLEX
    For e.g we solve matrix1, matrix2, matrix3, and so on till matrix N.
    We want to decrease the total speed of the solve, since sometimes it can take upto 10+ hours to solve all these objectives
    Typically we find that the solve time increases in some of the later objectives. 
    for e.g. a few objectives/matrices can account for maybe 50%+ of the total time of the solve.
    So reducing the runtime for these objectives can reduce total runtime
    There could be round off error causing problems with the later objectives.
    If we check the kappa, condition number of the solve v/s the matrix number, we see that for some later matrix where the runtime is high,
    the kappa number is high > 1e+11, 
    There are small changes being done from one matrix to another, mainly the objective changes and some bounds change,
    some round off error can also creep in
    But how can we find out/indentify which numbers in the matrix are contributing to this large increase in kappa?
    Can you give some suggestions on how to "limit" the kappa so that it does not go very high?


    Another question: in some cases in the solver log we see "Repairing basis singularity" Added to 1 columns superbasic list

    Iteration: 116089 Objective = 394364959.655557
    Repairing basis singularity.
    Added to 1 columns superbasic list.
    Markowitz threshold set to 0.2
    Iteration: 116552 Scaled infeas = 192.606291
    Iteration: 116554 Objective = 394364958.608593

    These messages also seem to be correlated to slowdown in the solve
    What do these messages mean, and are there any suggestions on how to avoid basis becoming singular?
    Are there any suggestions for identifying the data in the matrix that causes this problem and how to make changes in the data to avoid this problem?

    Please note that this is not coming from the initial business data, these changes which cause these issues are likely happening due to some round off/numerical proprocessing between the solves, but i dont know how to identify the problematic data/prevent these problems from happening

    Can you please give some recommendations/guidance on how to prevent these problems?

    Thanks in advance
    D

    ------------------------------
    Lukka D
    ------------------------------

    #DecisionOptimization


  • 2.  RE: How do we control kappa number from increasing, how to trace what numbers cause kappa increase?

    IBM Champion
    Posted Wed December 08, 2021 11:57 AM
    You might start by setting the data check parameter to 2. If CPLEX issues any warnings for the slow models, that might point you in a useful direction.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------

    Original Message


  • 3.  RE: How do we control kappa number from increasing, how to trace what numbers cause kappa increase?

    Posted Wed December 08, 2021 02:23 PM
    Hi Prof Paul Rubin
    Thank you for your response.

    With datacheck2, these seem to be the types of warnings that are seen

    CPLEX Warning 1004: Detected lower bound <= CPX_MINBOUND at variable 'SOUTMIN0143T022'.
    CPLEX Warning 1006: Detected upper bound <= CPX_MINBOUND at variable 'XBAL040217T009'.
    CPLEX Warning 1043: Detected righthand side <= the value of CPX_PARAM_EPRHS at constraint 'CAP0230T023#7'.
    CPLEX Warning 1008: Detected righthand side <= CPX_MINBOUND at constraint 'CAP0147T050#1618'.
    CPLEX Warning 1045: Detected nonzero <= the maximum value of either CPX_PARAM_EPRHS or CPX_PARAM_EPOPT at constraint 'CAP0102T007#401', variable 'F000634000040131'.
    CPLEX Warning 1036: Decimal part of coefficient for variable 'XBD00A044545T037' in obj looks like 56/81 in single precision.

    I am a newbie, so i dont know how to solve these.
    Can i get some hints on what needs to be implemented in the application to avoid these numerical problems?
    For e.g. are there examples (before adjustment and after adjustment) that show how these kind of warnings can be avoided?
    Do we need to implement CPX_MINBOUND?
    would cpxcleanup help in removing very small numbers? (and solve most of the warnings above)?

    ------------------------------
    Lukka D
    ------------------------------

    Original Message


  • 4.  RE: How do we control kappa number from increasing, how to trace what numbers cause kappa increase?

    IBM Champion
    Posted Wed December 08, 2021 03:26 PM
    CPX_MINBOUND (defined in the cpxconst.h header file -- I had to do a bit of digging to find it) is set to 1e-13. Quoting the associated comment: "Any bound smaller than or equal to this can be a potential source of ill-conditioning or numerical instability in a model." In other words, some of your variable bounds are too small to be safe. CPX_PARAM_EPRHS is the tolerance CPLEX uses for testing whether a constraint is satisfied. The default is 1e-6, but you can adjust that to some extent. (It cannot be set less than 1e-9.) Those warnings basically mean that you have nonzero right hand sides in constraints that CPLEX will not be able to distinguish from zero.

    It seems to me that your problem parameters are probably poorly scaled. You might look at whether rescaling some of your variables (changing watts to kilowatts or megawatts, kilometers to meters, ...) would alleviate the problems. Two other things to look at: are you trying to be overly precise (for instance, trying to force a variable to be nonzero while letting it get really really really close to zero); and are you using a "big M" somewhere in your model (for instance, as a coefficient in a penalty term) where a not-so-big M would do.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------

    Original Message


  • 5.  RE: How do we control kappa number from increasing, how to trace what numbers cause kappa increase?

    Posted Thu December 09, 2021 02:59 PM
    Hi Prof Paul Rubin

    Thank you so much for your helpful response.
    Thanks for finding out the CPX_MINBOUND value of 1.e-13.  Yes, some of the bounds, RHS are coming less than this number
    some Examples

    1) CPLEX Warning 1004: Detected lower bound <= CPX_MINBOUND at variable 'SOUTMAX0110T018'.
    SOUTMAX0110T018 >= 7.105427357601e-15    -->ideally this should be rounded to 0 (likely this is due to round off error)
    2) CPLEX Warning 1006: Detected upper bound <= CPX_MINBOUND at variable 'XBAL040217T009'.
    0 <= XBAL040217T009 <= 5.16987882845642e-26  -->this also likely should be rounded to 0 (likely this is due to round off error)
    3) CPLEX Warning 1043: Detected righthand side <= the value of CPX_PARAM_EPRHS at constraint 'CAP0230T023#7'.
    CAP0230T023#7: - CAP0230BD00T023 + 1.00029343369202 CAP0117BD00T023
    + 1.2963795474 ST0101024321T022
    + 1.2963795474 ST0201125775T022
    + 1.2963795474 OP064036T023
    + 1.2963795474 OP064639T022
    + 1.2963795474 ST0101068817T022
    + 1.2963795474 OP108202T023 = 7.65763047478996e-10   --->this also should be rounded to 0
    4) CPLEX Warning 1045: Detected nonzero <= the maximum value of either CPX_PARAM_EPRHS or CPX_PARAM_EPOPT at constraint 'CAP0102T007#401', variable 'F000634000040131'.
    CAP0102T007#401: - CAP0102BD00T007
    + 7.61760146968657e-7 F000634000040131   --->it seems even if coefficient is smaller than EPRHS/EPOPT then it can cause a problem? i was not sure if this also needs to be rounded down to 0.  i may need to check this
    + 1.01996377055621 OP076757T007 = -4153.02193820788  

    We are not using any Big-M in the model, but there are some "changes" being done between solves and these changes/fixings seem to be causing some small round off errors giving these numbers, since they appear in the later matrix solves

    I think u are recommending that these small numbers be zeroed out (say numbers smaller than 1.0e-6 or say 1.0e-7 can be zeroed out), and then we can check if this reduces the kappa and finally makes the solve faster.  Would these kind of changes (zeroing out small numbers) also prevent the "Repairing basis singularity" message? 
    Is there any way in interactive CPLEX to zero out constraint rhs, smaller than a threshold? or zero out bounds (lower or upper) which are smaller than a threshold?  is cpxcleanup something that can be invoked in interactive cplex? if yes what is the syntax? i could not find cpxcleanup in interactive cplex commands.  Basically i want to do something like if rhs < 1.0e-6, zero it out, can something like this be done in interactive cplex? if yes how to do it?

    In any case, i would like to thank you for all your helpful responses. Thank you.  i think u have answered my questions

    ------------------------------
    Lukka D
    ------------------------------

    Original Message


  • 6.  RE: How do we control kappa number from increasing, how to trace what numbers cause kappa increase?

    IBM Champion
    Posted Thu December 09, 2021 03:25 PM
    Yes, if the small numbers are "decimal dust" (rounding error), meaning that the model is valid when they are replaced by zero, I would try that. It might very well eliminate the basis singularity message, although the only way to be certain is to try. As far as the interactive optimizer goes, try the command "change values", which I think will ask you for a tolerance amount.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------

    Original Message