Originally posted by: AdamAugusta

*   640+   14                           -0.9540       -0.8268     7589   13.34%
*   640+    9                           -0.9470       -0.8268     7589   12.70%
*   640+    0                           -0.5232       -0.8268     7589  -58.04%
    640     2        0.0000    53       -0.5232       -0.8268     7589  -58.04%
Elapsed real time =  43.94 sec. (tree size = 28.78 MB, solutions = 118)
*  7934+ 6775                           -0.5060       -0.8268    26995  -63.40%
[...]
  14493 13005        0.0000    85       -0.0948       -0.8268    46712 -772.07%
* 14499+13007                           -0.0884       -0.8268    46728 -835.43%
* 14499+13007                           -0.0874       -0.8268    46728 -846.47%
* 14499+13007                           -0.0873       -0.8268    46728 -846.96%
* 14505+13007                           -0.0219       -0.8268    46750     ---
* 14505+13007                           -0.0164       -0.8268    46750     ---
* 14505+13007                           -0.0158       -0.8268    46750     ---

I'm not sure how to interpret this. What are the implications of a negative optimality gap?

The first thing I would check for is numerical instability in the problem. Turn on the option to collect kappa statistics, run the solver for a while (at least long enough to see negative gaps), kill the solver and check the distribution of stable/unstable bases.

Even though the problem may be numerics this still looks rather odd. What version of CPLEX do you use? Are you using any non-default parameter settings? Could you provide a SAV file of the model that exhibits this behavior?

Originally posted by: AdamAugusta

Unfortunately, I'm prohibited from sharing the model. I first saw this behavior in 12.2, but I'm also seeing it in 12.6. I'll try PaulRubin's recommendation.