Problems with MIQCP: Gurobi doesn't find the optimal solution

[Sébastien Auroux]

Dear all,

I am currently working with a quite complex MIQCP that I am solving with Gurobi (implemented with Python and Pyomo). Further, I have developed a good working heuristic algorithm for the same problem. 

The issue I have: While evaluation the MIQCP versus the heuristic algorithm, I have discovered that for very few instances (like 10 out of 2000) the heuristic algorithm performs better than the MIQCP solved by Gurobi. Of course this should not happen, as the MIQCP solution is supposed to be optimal (right?). At first I assumed to have some small implementation error, but then I took one of the affected instances and took a detailed look at the provided solutions:

Gurobi solution: -5277.0

heuristic solution: -5278.0

Now comes the weird part: I tried to fix some variables to "push" Gurobi towards the solution found by the heuristic algorithm, and indeed, Gurobi then found one solution with objective value -5278.0.

If I'm not wrong this proves two things:

1. the solution found by the heuristic is indeed feasible.

2. Gurobi did not solve optimally before.

What is also important to say is, that I adjusted the Gurobi parametres as follows: 

opt.options['MIPGap'] = 0.0

opt.options['Threads'] = 1

opt.options['timelimit'] = 36000

opt.options['NumericFocus'] = 3

opt.options['MIPFocus'] = 2

So at least a too high MIPGap is definitely not the problem. Am I missing any other important parameter?

This is an outline from the Gurobi output (full Log is attached). Thanks for any help or advise!

Presolve removed 385 rows and 4 columns

Presolve time: 0.75s

Presolved: 10878 rows, 40798 columns, 96169 nonzeros

Variable types: 16 continuous, 40782 integer (40782 binary)

Presolve removed 168 rows and 9684 columns

Presolved: 10710 rows, 31114 columns, 80585 nonzeros

Root relaxation: objective -5.278938e+03, 5818 iterations, 0.85 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work

 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0 -5278.9375    0    1          - -5278.9375     -      -    3s

     0     2 -5278.9375    0    1          - -5278.9375     -      -    4s

     1     3 -5278.9375    1   38          - -5278.9375     -   4797    5s

*   34    22              31    -5277.000000 -5278.9375  0.04%   290   10s

    94    39 -5278.0000    8   52 -5277.0000 -5278.9375  0.04%   163   15s

   129    60 -5278.9357    6   22 -5277.0000 -5278.9375  0.04%   206   20s

   246    92 -5277.9984    7   17 -5277.0000 -5278.9375  0.04%   148   25s

   299   106 -5277.9956   30   49 -5277.0000 -5278.9375  0.04%   141   30s

   343   122 -5278.9358   15   20 -5277.0000 -5278.9375  0.04%   142   35s

   409   140 -5277.9969   19   49 -5277.0000 -5278.9375  0.04%   130   40s

   447   152 -5278.0000   13  259 -5277.0000 -5278.9375  0.04%   137   45s

   480   169 -5277.9970   18   46 -5277.0000 -5278.9375  0.04%   145   50s

   564   184 -5277.9974   17   49 -5277.0000 -5278.9359  0.04%   131   55s

   603   186 -5277.9984   22   18 -5277.0000 -5278.9359  0.04%   128   62s

   606   190 -5278.0000   11  113 -5277.0000 -5278.9359  0.04%   164   65s

   620   198 -5278.9324   18   42 -5277.0000 -5278.9359  0.04%   172   70s

   647   209 -5277.9952   34   43 -5277.0000 -5278.9324  0.04%   175   75s

   691   204 -5277.9952   44   37 -5277.0000 -5278.9324  0.04%   166   80s

   758   192 -5277.9948   35   35 -5277.0000 -5278.0000  0.02%   156   85s

   827   169 -5278.0000   15  120 -5277.0000 -5278.0000  0.02%   147   90s

   913   160 -5278.0000   29  254 -5277.0000 -5278.0000  0.02%   142   95s

   970   161 -5278.0000   28  214 -5277.0000 -5278.0000  0.02%   142  100s

  1025   157 -5278.0000   17   96 -5277.0000 -5278.0000  0.02%   144  105s

  1098   145     cutoff   40      -5277.0000 -5278.0000  0.02%   142  110s

  1216   117 -5277.9948   33   66 -5277.0000 -5278.0000  0.02%   138  115s

  1276   116     cutoff   22      -5277.0000 -5278.0000  0.02%   142  120s

  1313   117     cutoff   30      -5277.0000 -5278.0000  0.02%   147  125s

  1341   121 -5278.0000   28  191 -5277.0000 -5278.0000  0.02%   150  130s

  1379   119 -5278.0000   33  242 -5277.0000 -5278.0000  0.02%   155  135s

  1439   108 -5277.9963   43  110 -5277.0000 -5278.0000  0.02%   155  140s

  1470   112 -5278.0000   19  311 -5277.0000 -5278.0000  0.02%   156  145s

  1515   118     cutoff   15      -5277.0000 -5278.0000  0.02%   157  150s

  1539   120 -5277.9963   35  325 -5277.0000 -5278.0000  0.02%   163  155s

  1570   118 -5278.0000   24  562 -5277.0000 -5278.0000  0.02%   167  160s

  1604   113 -5278.0000   28  242 -5277.0000 -5278.0000  0.02%   174  165s

  1656   112 -5277.9963   35  113 -5277.0000 -5278.0000  0.02%   176  170s

  1708   126 -5278.0000   26  336 -5277.0000 -5278.0000  0.02%   178  175s

  1757   121 -5278.0000   28  442 -5277.0000 -5278.0000  0.02%   181  180s

  1787   117     cutoff   24      -5277.0000 -5278.0000  0.02%   187  185s

  1806   111 -5278.0000   20  363 -5277.0000 -5278.0000  0.02%   192  191s

  1829   118 -5278.0000   31  690 -5277.0000 -5278.0000  0.02%   194  195s

  1885    76     cutoff   25      -5277.0000 -5277.9963  0.02%   197  200s

  1919    42     cutoff   18      -5277.0000 -5277.9952  0.02%   203  205s

Cutting planes:

  Cover: 184

  Implied bound: 14

  Clique: 248

  Flow cover: 11

  Zero half: 4

Explored 1962 nodes (419252 simplex iterations) in 208.47 seconds

Thread count was 1 (of 4 available processors)

Optimal solution found (tolerance 0.00e+00)

Best objective -5.277000000000e+03, best bound -5.277000000000e+03, gap 0.0%

[Jakob Sch.]

Hi,

As you can see form the log gurobi is heavily trying to achieve a positive semidefinite matrix. Thus, your problem seems to be right "on the edge of positive semidefiniteness". You might want to play around a bit with the parameters PSDTol and PreQLinearize. Can you provide a MPS file of your model? This would help to check whether numerical problems cause the solution to be computed falsely.

Best regards,
Jakob

[S. Auroux]

Hi,

thanks a lot for your helpful reply! Indeed I just obtained -5278.0 (tolerance 1.00e-10) by setting the PSDTol to 0.0.

You can find the MPS file here: https://drive.google.com/file/d/0B1p5bvUy05SUYnlzZXlmUUJDUUE/view?usp=sharing

[Robert Fourer]

Looking at the end of the log, it appears that the lower bound creeps up
from -5278.0000 to -5277.9952, with the result that the solution of -5277
appears to be optimal. Since you have an MIQCP I imagine that Gurobi's
barrier algorithm is being used to solve the subproblems. Gurobi's
convergence tolerance on the relative difference between primal and dual
objective values for barrier algorithms when solving problems with quadratic
constraints defaults to 1e-6, as do Gurobi's primal and dual feasibility
tolerances, and the default integer feasibility tolerance is 1e-5. Thus not
surprisingly, the "wrong" objective value of -5277.9963 is correct to about
6 places. If you experiment with tightening up the tolerances, you may find
that the lower bound stays closer to -5278.0000 and that this problem
disappears.

Bob Fourer
4...@ampl.com

=======

This is an outline from the Gurobi output ...

Presolve removed 385 rows and 4 columns
Presolve time: 0.75s
Presolved: 10878 rows, 40798 columns, 96169 nonzeros
Variable types: 16 continuous, 40782 integer (40782 binary)
Presolve removed 168 rows and 9684 columns
Presolved: 10710 rows, 31114 columns, 80585 nonzeros

Root relaxation: objective -5.278938e+03, 5818 iterations, 0.85 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0 -5278.9375    0    1          - -5278.9375     -      -    3s
     0     2 -5278.9375    0    1          - -5278.9375     -      -    4s
     1     3 -5278.9375    1   38          - -5278.9375     -   4797    5s
*   34    22              31    -5277.000000 -5278.9375  0.04%   290   10s
    94    39 -5278.0000    8   52 -5277.0000 -5278.9375  0.04%   163   15s

.......

  1806   111 -5278.0000   20  363 -5277.0000 -5278.0000  0.02%   192  191s
  1829   118 -5278.0000   31  690 -5277.0000 -5278.0000  0.02%   194  195s
  1885    76     cutoff   25      -5277.0000 -5277.9963  0.02%   197  200s
  1919    42     cutoff   18      -5277.0000 -5277.9952  0.02%   203  205s

[Jakob Sch.]

Am Samstag, 18. Oktober 2014 17:22:05 UTC+2 schrieb Bob Fourer:

Since you have an MIQCP I imagine that Gurobi's
barrier algorithm is being used to solve the subproblems.

Probably not, since simplex iteration count is given in the log (second last column). Usually gurobi chooses automatically and (in all cases that I encountered) it used the outer approximation method for solving MIQCPs. You can change this by setting the MIQCPMethod parameter.

Best regards,
Jakob