1

this is a follow-up question to this question: Interpretation of GAP in CPLEX

I used the following Expression at the beginning of my optimization (min) problem:

execute gapTermination {
    cplex.epgap = 0.00; // result at gap of 0%  
   }

This is a part of the engine log:

        Nodes                                         Cuts/
    Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0      560.7929   100                    560.7929      115         
      0     0      742.1396    57                   Cuts: 121      214         
      0     0      744.3119    61                    Cuts: 10      226         
      0     0      747.2193    61                    Cuts: 10      233         
      0     0      747.2797    61                      MCF: 1      234         
*     0+    0                          916.3811      747.2797            18.45%
      0     2      747.2797    61      916.3811      747.2797      234   18.45%

Elapsed time = 0.13 sec. (49.77 ticks, tree = 0.00 MB, solutions = 1)
*   916   755      integral     0      778.9609      753.8931     7249    3.22%
*  4739  1918      integral     0      771.9166      759.5332    25884    1.60%

Cover cuts applied:  5
Implied bound cuts applied:  8
Flow cuts applied:  27
Mixed integer rounding cuts applied:  36
Multi commodity flow cuts applied:  1
Gomory fractional cuts applied:  22

Root node processing (before b&c):
  Real time             =    0.11 sec. (49.41 ticks)
Parallel b&c, 16 threads:
  Real time             =    0.38 sec. (202.30 ticks)
  Sync time (average)   =    0.07 sec.
  Wait time (average)   =    0.07 sec.
                      ------------
Total (root+branch&cut) =    0.49 sec. (251.71 ticks)

As you can see, the "optimal" solution seems to be found, but it still has a gap of 1,60%.

How to Interpret this? My thought would be, that I found the optimal integer solution (no single integer solution left that's better), but the non-integer value achieves an even better result being 1.60% lower (minimization Problem).

If my thought is correct, then it would mean that a 0.00% gap can only be achieved if the optimum of the relaxed solution (usually non-integer) happens to be an integer value.

I'd really appreciate if someone could help me out here. Thanks in advance.

Riegsche
  • 101
  • 1
  • 5
  • 1
    Check the docs of cplex how to read out the gap of a solution. **The 1.60% is probably the gap of a solution which is not the final solution**. A MIP-solver, targeting a Gap X (correctly stated in terms of API) should never return a worse solution with a successful flag! And no, the gap is always in terms of valid solutions, not based on relaxations and co. If the problem has a solution, reaching gap ```epsilon``` is always possible given some long enough finite time. – sascha Mar 31 '17 at 16:12
  • 1
    You could try logging extra detail, or with more frequency. By default cplex will output only every N nodes explored in the B&B tree, as well as when it finds a new (improved) integer solution. It may have found that 771.9166 solution then carried on the B&B search, moving the best bound until it reached a tiny enough gap to be judged 'optimal'. So the actual bound may have moved very close to that integer solution's value, but you may not be seeing it in the log. – TimChippingtonDerrick Apr 01 '17 at 22:35

0 Answers0