CODEWITHSUNDEEP
optimizationcplex
Chthonic Project
Chthonic Project

Reputation: 8356

How to interpret the output of the CPLEX interactive optimizer?

I have been using the CPLEX interactive optimizer to solve some linear programming problems. I generate the problem, use the read command from CPLEX, and then run optimize. For some problems, CPLEX produces a solution within an hour and I use write <filename> sol to obtain the complete solution. For some problems, however, it seems to get stuck after a point. The output I see looks like this:

       Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
    .        .        .        .        .        .        .        .        .
    .        .        .        .        .        .        .        .        .
    .        .        .        .        .        .        .        .        .
Elapsed time = 816.06 sec. (429933.56 ticks, tree = 8.58 MB, solutions = 13)
   2884  1809       87.6482 12159      201.6200       80.3540  2100428   60.15%
   2938  1863      102.4825 11621      201.6200       80.3540  2149201   60.15%
   3727  2616       93.1194 10858      201.6200       80.3540  2409711   60.15%
   3743  2632       92.6249 11845      201.6200       80.3540  2437316   60.15%
   3767  2656       91.7097 12044      201.6200       80.3540  2466252   60.15%
   3803  2692       91.8088 11972      201.6200       80.3540  2491113   60.15%
   3805  2694      101.4411 10242      201.6200       80.3540  2497951   60.15%
   3827  2716       91.7697 12003      201.6200       80.3540  2522926   60.15%
   3937  2826      102.6357  7167      201.6200       80.3540  2676145   60.15%
   4175  3056       94.0081  9159      201.6200       83.9275  2783878   58.37%
Elapsed time = 930.33 sec. (472066.00 ticks, tree = 20.04 MB, solutions = 13)
   4178  3059       88.0621 11735      201.6200       83.9275  2788962   58.37%
   4190  3071       87.5922 11461      201.6200       83.9275  2809216   58.37%
   4202  3083       87.7980 11585      201.6200       83.9275  2823899   58.37%
   4214  3095       87.9296 11733      201.6200       83.9275  2841065   58.37%
   4215  3096       92.6440 11647      201.6200       83.9275  2844197   58.37%
   4227  3108       94.0457 12069      201.6200       83.9275  2869047   58.37%
   4239  3119       93.3760 11843      201.6200       83.9275  2890566   58.37%
   4251  3131       94.2709 11724      201.6200       83.9275  2916710   58.37%
   4274  3153       92.6187 11640      201.6200       83.9275  2945659   58.37%
   4286  3163       91.6257 11632      201.6200       83.9275  2965344   58.37%
Elapsed time = 998.66 sec. (493988.99 ticks, tree = 20.09 MB, solutions = 13)
   4310  3186       91.8091 10453      201.6200       83.9275  3010401   58.37%
   4323  3199       96.4584 11813      201.6200       83.9275  3034842   58.37%
   4335  3211       96.1343 11849      201.6200       83.9275  3057500   58.37%
   4359  3234       96.8602 11609      201.6200       83.9275  3092422   58.37%

In the beginning, the last column has a higher number (e.g., 99.92%), which starts decreasing quickly. But after a certain point, the last gap column keeps stating 58.37% without further reduction. What does this value signify? My understanding is that this is the percentage difference between the current optimal solution and the global optimum. (i.e., x% means that if I stop the optimization at this point, the solution returned is provably within x% of the global optimum).

Is my understanding correct? Also, what can I do to understand and debug/get-around this phenomenon of "getting stuck"?

Upvotes: 1

Views: 1139

Answers (1)

David Nehme
David Nehme

Reputation: 21572

The % gap is the relative difference between the best solution and the best known bound for a solution. This is guaranteed to be higher than the gap between the best known solution and the true global optimum. In your case, the best bound is 83.9275, the best bound is 201.62, and you are minimizing so the gap is 

1 - (83.9275 / 201.62)  =  .5837

The "stuck" behavior you see is quite common when solving a difficult mixed-integer problem. It's possible that the solution you have is actually close to optimal, but the bound isn't tight, or that your solution is truly far the optimal, but CPLEX is unable to find anything better. There are a lot of methods for trying to solve this problem. Among them are

  • Improve your MIP formulation
  • Try different parameters (turn up cuts, probing, switch to strong branching, ...)
  • See if another solver works better on your problem (gurobi or xpressmp)

Upvotes: 1

Related Questions