Issue when getting dual optimal solution for an MIQCP model

Dear Sir or Madam,

I am solving multi-time-period pooling problems (nonconvex MIQCP with binaries) using GUROBI. While GUROBI can quickly find a primal optimal solution within the predefined tolerance, GUROBI runs into problems when trying to find a corresponding optimal dual solution. I see a few kinds of warnings from GUROBI when trying a number of instances; these warnings include:

1. Fixed MIQCP status(12): Optimization was terminated due to unrecoverable numerical difficulties.

2. Warning: failed to compute QCP dual solution

3.Warning: failed to compute QCP dual solution due to inaccurate barrier solution. Try decreasing BarQCPConvTol for more accuracy

Below I give the log file for a case when the first item above was encountered:

Gurobi           42.1.0 cb854401 Feb 1, 2023           LEG x86 64bit/Linux    

Gurobi link license.
Set parameter OutputFlag to value 1
Gurobi library version 10.0.0
Reading parameter(s) from "/scratch/gpfs/ys5998/toDella_gP/gurobi.opt"
>>  nonconvex 2
Finished reading from "/scratch/gpfs/ys5998/toDella_gP/gurobi.opt"
Set parameter TimeLimit to value 7200
Set parameter MIPGap to value 0.01
Set parameter MIPGapAbs to value 0
Set parameter NonConvex to value 2
Set parameter Threads to value 1
--- GMO Q Extraction (ThreePass): 0.00s
--- GMO setup time: 0.00
Set parameter QCPDual to value 1
Space for names approximately 0.15 Mb
Use option 'names no' to turn use of names off
Starting Gurobi...
Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (linux64)

CPU model: Intel(R) Xeon(R) Gold 6242 CPU @ 2.80GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 32 physical cores, 32 logical processors, using up to 1 threads

Optimize a model with 3214 rows, 656 columns and 13240 nonzeros
Model fingerprint: 0x23f63725
Model has 288 quadratic constraints
Variable types: 528 continuous, 128 integer (128 binary)
Coefficient statistics:
  Matrix range     [8e-02, 1e+03]
  QMatrix range    [1e+00, 1e+00]
  QLMatrix range   [1e+00, 1e+00]
  Objective range  [1e+00, 1e+01]
  Bounds range     [1e+00, 1e+02]
  RHS range        [1e+00, 1e+03]
Presolve removed 1474 rows and 102 columns
Presolve time: 0.03s
Presolved: 2828 rows, 554 columns, 9070 nonzeros
Presolved model has 272 bilinear constraint(s)
Variable types: 444 continuous, 110 integer (110 binary)
Extra simplex iterations after uncrush: 7

Root relaxation: objective -7.698641e+02, 1341 iterations, 0.05 seconds (0.07 work units)

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

     0     0 -769.86412    0  111          - -769.86412      -     -    0s
     0     0 -767.57928    0  130          - -767.57928      -     -    0s
     0     0 -767.46516    0  138          - -767.46516      -     -    0s
     0     0 -765.96855    0  154          - -765.96855      -     -    0s
     0     0 -765.95513    0  130          - -765.95513      -     -    0s
     0     0 -765.93298    0  187          - -765.93298      -     -    0s
     0     0 -765.88693    0  154          - -765.88693      -     -    0s
     0     0 -765.77000    0  140          - -765.77000      -     -    0s
     0     0 -765.76684    0  139          - -765.76684      -     -    0s
     0     0 -765.75866    0  166          - -765.75866      -     -    0s
     0     0 -765.74248    0  163          - -765.74248      -     -    0s
     0     0 -765.69325    0  170          - -765.69325      -     -    0s
     0     0 -765.66987    0  173          - -765.66987      -     -    0s
     0     0 -765.65693    0  167          - -765.65693      -     -    0s
     0     0 -765.63969    0  175          - -765.63969      -     -    0s
     0     0 -765.62595    0  195          - -765.62595      -     -    0s
     0     0 -765.61936    0  195          - -765.61936      -     -    0s
     0     0 -765.61347    0  200          - -765.61347      -     -    0s
     0     0 -765.61311    0  203          - -765.61311      -     -    0s
     0     0 -765.61004    0  236          - -765.61004      -     -    0s
     0     0 -765.61002    0  236          - -765.61002      -     -    0s
     0     0 -765.60933    0  233          - -765.60933      -     -    0s
     0     0 -765.60933    0  206          - -765.60933      -     -    0s
     0     2 -765.59453    0  198          - -765.59453      -     -    1s
   528   298 -758.92716   18   30          - -763.86908      -  45.7    5s
   701   370 -757.56675   38  106          - -763.84378      -  62.0   10s
  1562   639 -698.27496   93   29          - -762.35594      -  54.1   15s
H 1588   561                    -699.5711356 -762.35594  8.97%  53.2   15s
  2223   839 -744.78889   42   23 -699.57114 -761.48318  8.85%  55.1   20s
* 2319   911             125    -699.5895004 -761.48318  8.85%  53.0   20s
* 2321   911             126    -699.5976247 -761.48318  8.85%  53.0   20s
* 2322   910             126    -699.6005026 -761.48318  8.85%  52.9   20s
* 2326   910             125    -699.6021321 -761.48318  8.85%  52.9   20s
* 2327   909             125    -699.6021527 -761.48318  8.85%  52.8   20s
H 2333   826                    -701.6564940 -761.43320  8.52%  53.0   20s
H 2464   808                    -738.6574189 -761.40511  3.08%  53.4   21s
  2947  1013 -758.03351   30   49 -738.65742 -761.00723  3.03%  54.7   25s
H 3037   952                    -744.5933126 -761.00723  2.20%  54.0   25s
H 3126  1003                    -744.5933127 -760.98360  2.20%  53.6   25s
  3765  1258 -759.02857   24   66 -744.59331 -760.59117  2.15%  52.2   30s
H 3843  1288                    -744.7922617 -760.56102  2.12%  52.8   30s
H 4019  1448                    -744.7922631 -760.56102  2.12%  51.0   31s
H 4175  1590                    -744.7922633 -760.56102  2.12%  49.3   32s
H 4201  1616                    -744.7922635 -760.56102  2.12%  49.0   32s
* 4676  1425             158    -751.9146883 -760.56102  1.15%  44.5   33s
  4942  1480 -757.83940   30   78 -751.91469 -760.50610  1.14%  44.7   35s
  5598  1660 -758.89312   34   56 -751.91469 -760.33984  1.12%  46.4   40s
  6391  1964 -755.22609   55   36 -751.91469 -760.18656  1.10%  46.2   45s
* 6669  1373             128    -754.8629739 -760.18656  0.71%  44.4   45s

Cutting planes:
  Learned: 6
  Gomory: 20
  Cover: 16
  Implied bound: 16
  Projected implied bound: 2
  MIR: 100
  StrongCG: 2
  Flow cover: 144
  Inf proof: 3
  Zero half: 2
  RLT: 144
  Relax-and-lift: 9

Explored 6670 nodes (299970 simplex iterations) in 45.65 seconds (29.37 work units)
Thread count was 1 (of 32 available processors)

Solution count 10: -754.863 -751.915 -744.792 ... -699.602

Optimal solution found (tolerance 1.00e-02)
Best objective -7.548629739438e+02, best bound -7.601865561753e+02, gap 0.7052%

User-callback calls 31531, time in user-callback 0.04 sec
MIQCP status(2): Model was solved to optimality (subject to tolerances).

Solving fixed MIQCP.
Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (linux64)

CPU model: Intel(R) Xeon(R) Gold 6242 CPU @ 2.80GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 32 physical cores, 32 logical processors, using up to 1 threads

Optimize a model with 3214 rows, 656 columns and 13240 nonzeros
Model fingerprint: 0xa70358ee
Model has 288 quadratic constraints
Coefficient statistics:
  Matrix range     [8e-02, 1e+03]
  QMatrix range    [1e+00, 1e+00]
  QLMatrix range   [1e+00, 1e+00]
  Objective range  [1e+00, 1e+01]
  Bounds range     [8e-04, 1e+02]
  RHS range        [1e+00, 1e+03]
Presolve removed 2693 rows and 423 columns
Presolve time: 0.00s
Presolved: 721 rows, 235 columns, 2041 nonzeros
Ordering time: 0.00s

Barrier statistics:
 AA' NZ     : 4.899e+03
 Factor NZ  : 7.018e+03
 Factor Ops : 8.141e+04 (less than 1 second per iteration)
 Threads    : 1

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0   1.39303988e+04 -1.90253167e+04  1.37e+02 7.81e-01  3.22e+02     0s
   1   1.16887850e+03 -9.25151339e+03  1.70e+01 7.99e-08  4.56e+01     0s
   2   6.12153203e+02 -3.63684845e+02  1.13e+01 2.68e-07  2.56e+01     0s
   3   7.25965784e+01  5.32472586e+01  7.89e+00 1.16e-06  1.54e+01     0s
   4  -7.32798750e+02 -1.49651760e+03  1.98e-01 1.87e-06  7.61e-01     0s
   5  -7.43088884e+02  6.07152944e+03  1.05e-01 1.51e-06  8.90e-01     0s
   6  -7.44469488e+02 -8.82248690e+03  8.80e-02 1.98e-05  6.87e+00     0s
   7  -7.50410944e+02 -2.54805160e+04  1.38e-02 2.37e-05  6.29e-01     0s
   8  -7.51536309e+02 -2.77372839e+04  6.21e-04 4.07e-06  9.60e-02     0s
   9  -7.51558860e+02 -2.91721164e+04  2.92e-04 2.82e-06  2.50e-02     0s
  10  -7.51562111e+02 -2.86868653e+04  2.10e-04 6.39e-05  1.59e-02     0s
  11   4.10764763e+05 -1.54841768e+06  4.00e+03 1.13e+01  6.71e+05     0s
  12   1.86988642e+03 -6.58053803e+04  2.45e+01 6.22e+00  3.69e+02     0s
  13   6.61798466e+02 -2.53788912e+04  1.28e+01 3.04e+00  1.07e+02     0s
  14  -1.45993014e+02 -4.55296273e+03  4.83e+00 6.00e-01  3.15e+01     0s
  15  -4.20509900e+02  3.10096896e+03  1.58e+00 1.75e-04  2.41e+02     0s
  16  -5.51663593e+02  1.95280029e+05  8.94e-01 2.50e-02  1.85e+04     0s
  17* -6.35916530e+02  3.44821057e+07  1.68e-04 7.30e-03  1.50e-01     0s
  18* -6.39871642e+02  1.01009657e+11  1.18e-07 1.74e-02  4.95e-04     0s
  19* -6.43219607e+02  2.37192193e+13  2.84e-11 1.33e-02  8.57e-07     0s
  20* -6.57606129e+02  8.80895695e+17  1.17e-14 1.97e-01  4.34e-10     0s
  21* -6.61439242e+02  5.85714076e+20  5.81e-18 3.64e+00  5.36e-13     0s
  22* -6.61397019e+02  3.69463555e+25  2.00e-21 2.05e+01  4.06e-15     0s
  23* -6.61401146e+02  4.65190460e+25  6.43e-22 3.41e+02  4.20e-15     0s
  24* -6.61409152e+02  1.92105687e+28  1.41e-25 3.99e+02  1.01e-18     0s
  25* -6.61526472e+02  8.78823302e+31  4.72e-29 7.01e+01  2.26e-22     0s
  26* -6.61908454e+02  2.87354203e+32  4.71e-29 2.44e+02  6.08e-22     0s
  27* -6.56869141e+02  1.15655317e+33  3.67e-29 3.31e+02  6.62e-23     0s
  28* -6.51211611e+02  1.99172969e+33  3.69e-29 5.96e+01  3.56e-23     0s
  29* -6.42362663e+02  3.33721621e+33  3.71e-29 6.27e+01  1.96e-23     0s
  30* -6.29691117e+02  1.15022014e+34  3.75e-29 2.83e+01  1.67e-23     0s
  31* -5.95650894e+02  6.49459383e+34  3.80e-29 5.68e+01  1.70e-23     0s
  32* -4.86669766e+02  4.89912235e+35  3.86e-29 3.30e+01  2.02e-23     0s
  33* -2.16762296e+02  3.41811590e+36  3.90e-29 8.95e+01  2.78e-23     0s
  34*  9.20336186e+02  4.97673441e+38  4.01e-29 1.84e+03  5.04e-22     0s
  35*  9.20337146e+02  4.97669513e+38  4.01e-29 1.38e+03  5.04e-22     0s
  36*  9.20337146e+02  8.81864573e+39  4.01e-29 1.21e+05  2.21e-20     0s

Barrier performed 36 iterations in 0.02 seconds (0.01 work units)
Numerical trouble encountered


User-callback calls 31674, time in user-callback 0.04 sec
Fixed MIQCP status(12): Optimization was terminated due to unrecoverable numerical difficulties.
Fixed MIQCP did not return with an optimal solution. Reporting primal solution only.

MIQCP Solution:       -754.862974    (299970 iterations, 6670 nodes)
Best possible:        -760.186556
Absolute gap:            5.323582
Relative gap:            0.007003

--- Reading solution for model mP[LST:1676]
***
*** Solver did not provide marginals for model mP
***
--- gms58_3_3_gP.gms(536) 5 Mb  45 secs[FIL:"/scratch/gpfs/ys5998/toDella_gP/gms58_3_3_gP.gms",536,0]
--- Executing after solve: elapsed 0:00:45.832[LST:6032]
--- gms58_3_3_gP.gms(537) 5 Mb[FIL:"/scratch/gpfs/ys5998/toDella_gP/gms58_3_3_gP.gms",537,0]
                                                                                            
--- gms58_3_3_gP.gms(583) 5 Mb[FIL:"/scratch/gpfs/ys5998/toDella_gP/gms58_3_3_gP.gms",583,0]
--- GDX File (execute_unload) /scratch/gpfs/ys5998/toDella_gP/gms58_3_3_gP_result.gdx[FIL:"/scratch/gpfs/ys5998/toDella_gP/gms58_3_3_gP_result.gdx",0,0]
*** Status: Normal completion[LST:6048]
--- Job gms58_3_3_gP.gms Stop 05/10/23 22:20:09 elapsed 0:00:45.836

However, I also note that not all instances have such difficulties to compute optimal dual solution. I would say such problems happens more than 50% of all instances.

My questions are as follows:

1. What does the fixed MIQCP mean? Does it mean that GUROBI fix all binaries and solve a QCP?

2. What do you think the reason behind all these numerical difficulties when trying to find a dual optimal solution?

3. If I do not need the optimal dual solution, can I safely ignore this problem, and do you think the obtained primal optimal solution for my multiperiod pooling problem is still 100% accurate and reliable?

I very look forward to your reply!

Regards,

Yingkai Song

Jaromił Najman

Gurobi Staff

May 15, 2023 08:26
Edited

Hi Yingkai Song,

The message means that Gurobi fixes all binary variables in order to obtain a continuous model. Note that dual values are only well-defined for continuous models. If the fixed model is convex, then dual values can be computed.

This is a good question which I cannot answer without having a closer look at the model. Could you please share this particular instance as an MPS or LP file? Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.

Yes and (almost 100%) yes. Please note that you should always check whether the final optimal solution returned by Gurobi makes sense for your application. You should never just blindly trust any solver solution in an advanced real-world application. It is most often required that slight manual altering of the final solution point is needed to make the solution actually "real-world feasible". The reason is mainly of numerical nature where machine-precision inaccuracies can add up to something that is correct w.r.t. the algorithm but may not be perfectly accurate for your real-world system.

Best regards,
Jaromił

May 15, 2023 13:51

Hi Jaromil,

Many thanks for your thorough and detailed reply!

1 and 2: I should have recalled that the dual values in principle make sense when the fixed model is convex. However, my fixed MIQCP model is typically nonconvex due to bilinear terms. In this case, when Gurobi failed to compute dual values, do you think it may be because of my fixed model's nonconvexity? The following question may not be suitable here, but I tried to solve the same model using other generic MINLP solver such as BARON. However, I found that unlike Gurobi, BARON always gave me dual values, even though the fixed model is nonconvex. Do you have any insights for this?

3: Good to know! I am not dealing with a real-world problem. As long as I have global optimality which satisfies all my constraints (under mild tolerance for machine precision). Then, it is good enough.

Yingkai

May 16, 2023 07:57
Edited

Hi Yingkai,

1 and 2: I should have recalled that the dual values in principle make sense when the fixed model is convex. However, my fixed MIQCP model is typically nonconvex due to bilinear terms. In this case, when Gurobi failed to compute dual values, do you think it may be because of my fixed model's nonconvexity?

Yes, it is due to the nonconvexity. Currently, Gurobi does not compute dual values for nonconvex models. This will possibly be added in an upcoming release.

The following question may not be suitable here, but I tried to solve the same model using other generic MINLP solver such as BARON. However, I found that unlike Gurobi, BARON always gave me dual values, even though the fixed model is nonconvex. Do you have any insights for this?

Global MINLP solvers such as BARON or OCTERACT usually use a local solver such as, e.g., IPOPT, KNITRO, or CONOPT (or any own algorithm) to find feasible locally optimal solution points. These local solvers provide dual information about the locally optimal solution they find. This is the information that the global MINLP solver provides to the user.

If possible, could you please share this particular model anyway? I would like to have a look at what might be going wrong in the Barrier solve. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.

May 16, 2023 12:16

Sorry, since the code contains some of our unpublished work, I may not be able to share it with this community. This situation may change soon and I will let you know.

Thanks again for all your clarifications.

Best,

Issue when getting dual optimal solution for an MIQCP model

Comments

Didn't find what you were looking for?