Decision Optimization

 View Only

  • 1.  Interpretation of Optimality Gap

    Posted Wed December 02, 2020 09:31 AM
    Edited by System Fri January 20, 2023 04:28 PM
    Hi,

    I have a large-scale complex MILP model and use CPLEX. I set a time limit of 1.5 hours. Below I am sharing the last part of the engine log.

    Elapsed time = 5238.73 sec. (4365999.61 ticks, tree = 0.01 MB, solutions = 3)
    443 14 97.9331 133 27.7661 98.7403 2801188 255.61%
    444 15 97.9095 186 27.7661 98.7403 2805386 255.61%
    445 16 97.8858 160 27.7661 98.7403 2809131 255.61%
    446 17 97.8637 131 27.7661 98.7403 2812900 255.61%
    447 18 97.8363 219 27.7661 98.7403 2818286 255.61%
    448 19 97.7985 216 27.7661 98.7403 2821771 255.61%
    449 20 97.7458 192 27.7661 98.7403 2826195 255.61%
    450 10 cutoff 27.7661 98.2918 2891365 254.00%
    453 9 cutoff 27.7661 98.2918 2897139 254.00%

    Implied bound cuts applied: 414

    Root node processing (before b&c):
    Real time = 320.59 sec. (170265.87 ticks)
    Parallel b&c, 4 threads:
    Real time = 5079.64 sec. (4353692.30 ticks)
    Sync time (average) = 2770.81 sec.
    Wait time (average) = 0.02 sec.
    ------------
    Total (root+branch&cut) = 5400.23 sec. (4523958.17 ticks)


    I am curios what 255% optimality gap really implies. Shouldn't optimality gap between 0 and 100 percent or am I missing something? I have two more related questions. They are about the following line "(4365999.61 ticks, tree = 0.01 MB, solutions = 3)". 

    How is it possible that tree is really small (0.01 MB) after 90 minutes? What does solutions = 3 mean? 



    ------------------------------
    S Y
    ------------------------------
    #DecisionOptimization


  • 2.  RE: Interpretation of Optimality Gap
    Best Answer

    IBM Champion
    Posted Wed December 02, 2020 05:22 PM
    The gap is explained in the user's manual (CPLEX Optimizers > User's Manual for CPLEX > Discrete optimization > Solving mixed integer problems (MIP) > Progress reports: interpreting the node log. The gap formula is

    (best integer - best node) * objsen / (abs (best integer) + 1e-10)

    in which "objsen" is -1 if you are maximizing and +1 if you are minimizing (so basically the numerator is an absolute difference). Multiply by 100 to get the gap % as reported. So a 255% gap means that the best bound is 255% bigger (since you are maximizing) than the incumbent objective value.

    I believe that "Solutions = 3" means that three feasible solutions are in the solution pool. These are the feasible solutions that CPLEX finds during the search. They are not necessarily optimal.

    As for why your tree is so small, the next line says that CPLEX has looked at 443 nodes, of which 14 nodes are still alive (the rest having been pruned). Storing 14 nodes does not take all that much space, hence the small tree. The rather small number of nodes processed (443 in nearly 1.5 hours) is probably due in part to the size of your model, but may also indicate numerical problems.

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

    Original Message