Wednesday, April 1, 2015

More fun with quadratic models

This model seems to be solving just fine:

MODEL STATISTICS

BLOCKS OF EQUATIONS          81     SINGLE EQUATIONS           81
BLOCKS OF VARIABLES         127     SINGLE VARIABLES          127
NON ZERO ELEMENTS           361     NON LINEAR N-Z            240
DERIVATIVE POOL              20     CONSTANT POOL              56
CODE LENGTH                 782     DISCRETE VARIABLES         60

Gurobi           24.4.1 r50296 Released Dec 20, 2014 WEI x86 64bit/MS Windows

Gurobi full license.
Gurobi library version 6.0.0
Starting Gurobi...
Optimize a model with 20 rows, 126 columns and 60 nonzeros
Model has 60 quadratic objective terms
Model has 60 quadratic constraints
Coefficient statistics:
  Matrix range    [1e+00, 1e+00]
  Objective range [0e+00, 0e+00]
  Bounds range    [5e-01, 8e+00]
  RHS range       [1e+00, 1e+00]
Presolve time: 0.00s
Presolved: 20 rows, 126 columns, 60 nonzeros
Presolved model has 60 quadratic objective terms
Variable types: 66 continuous, 60 integer (60 binary)

Root relaxation: objective 0.000000e+00, 41 iterations, 0.00 seconds

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

H    0     0                      20.1386974    0.00000   100%     -    0s
     0     0   12.95963    0    6   20.13870   12.95963  35.6%     -    0s
     0     0 infeasible    0        20.13870   20.13870  0.00%     -    0s

Cutting planes:

Explored 0 nodes (377 simplex iterations) in 0.08 seconds
Thread count was 1 (of 8 available processors)

Optimal solution found (tolerance 0.00e+00)
Best objective 2.013869741063e+01, best bound 2.013869741063e+01, gap 0.0%
MIQCP status(2): Model was solved to optimality (subject to tolerances).

Solving fixed MIQCP.
Optimize a model with 20 rows, 126 columns and 60 nonzeros
Model has 60 quadratic objective terms
Model has 60 quadratic constraints
Coefficient statistics:
  Matrix range    [1e+00, 1e+00]
  Objective range [0e+00, 0e+00]
  Bounds range    [5e-01, 8e+00]
  RHS range       [1e+00, 1e+00]
Presolve removed 20 rows and 100 columns
Presolve time: 0.00s
Presolved: 246 rows, 260 columns, 560 nonzeros
Presolved model has 60 second-order cone constraints
Ordering time: 0.00s

Barrier statistics:
AA' NZ     : 6.030e+03
Factor NZ  : 6.276e+03
Factor Ops : 2.569e+05 (less than 1 second per iteration)
Threads    : 1

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0   5.95174921e+02 -2.20942251e+01  5.61e+00 5.24e+00  8.70e+00     0s
   1   7.73169938e+01 -9.09925343e+01  3.83e-01 5.80e-01  1.08e+00     0s
   2   2.61450398e+01 -5.66216921e+00  4.50e-02 7.46e-02  1.58e-01     0s
   3   2.18586349e+01  2.14234892e+00  7.66e-03 4.90e-02  9.78e-02     0s
   4   2.09341242e+01  6.68994751e+00  2.23e-03 3.59e-02  7.14e-02     0s
   5   2.04734405e+01  1.56421119e+01  4.98e-04 1.15e-02  2.39e-02     0s
   6   2.02435139e+01  1.92199379e+01  2.82e-05 2.18e-03  4.88e-03     0s
   7   2.01585476e+01  2.00900183e+01  1.20e-10 5.47e-05  2.70e-04     0s
   8   2.01393068e+01  2.01370266e+01  5.85e-10 1.50e-06  8.78e-06     0s
   9   2.01387075e+01  2.01386804e+01  4.13e-09 7.98e-08  9.68e-08     0s
  10   2.01386974e+01  2.01386961e+01  5.47e-10 7.04e-10  4.52e-09     0s

Barrier solved model in 10 iterations and 0.01 seconds
Optimal objective 2.01386974e+01

Solving KKT system to obtain QCP duals...

Optimize a model with 80 rows, 126 columns and 240 nonzeros
Coefficient statistics:
  Matrix range    [2e-03, 4e+00]
  Objective range [2e-01, 2e+01]
  Bounds range    [5e-01, 8e+00]
  RHS range       [1e-01, 1e+01]
Presolve removed 20 rows and 60 columns
Presolve time: 0.02s
Presolved: 60 rows, 66 columns, 180 nonzeros
Ordering time: 0.00s

Barrier statistics:
AA' NZ     : 5.700e+02
Factor NZ  : 6.300e+02
Factor Ops : 8.610e+03 (less than 1 second per iteration)
Threads    : 1

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0   1.64221433e+07 -1.74037374e+07  9.98e+02 5.00e+02  1.00e+06     0s
   1   3.06430913e+06 -3.96880437e+06  7.86e+02 1.97e+02  4.11e+05     0s
   2   7.41985462e+04 -1.37029670e+06  8.77e+01 2.58e+01  8.16e+04     0s
   3   7.82357071e+02 -1.08762827e+06  5.30e+00 1.62e+00  9.72e+03     0s
   4   4.89433799e+02 -5.28127121e+05  0.00e+00 1.62e-06  2.75e+03     0s
   5   4.84263108e+02 -2.44700888e+03  0.00e+00 6.77e-09  1.53e+01     0s
   6   1.49830346e+02 -3.22980351e+02  0.00e+00 7.99e-15  2.46e+00     0s
   7   4.73122148e+01 -5.45185139e+01  0.00e+00 1.78e-15  5.30e-01     0s
   8   2.37562000e+01  1.37551176e+01  0.00e+00 8.88e-16  5.21e-02     0s
   9   2.03314732e+01  1.97150561e+01  0.00e+00 8.88e-16  3.21e-03     0s
  10   2.01629353e+01  2.01091957e+01  0.00e+00 8.88e-16  2.80e-04     0s
  11   2.01421045e+01  2.01349098e+01  0.00e+00 8.88e-16  3.75e-05     0s
  12   2.01391804e+01  2.01381595e+01  0.00e+00 8.88e-16  5.32e-06     0s
  13   2.01387653e+01  2.01386209e+01  0.00e+00 1.78e-15  7.53e-07     0s
  14   2.01387066e+01  2.01386861e+01  0.00e+00 8.88e-16  1.07e-07     0s
  15   2.01386982e+01  2.01386953e+01  0.00e+00 1.78e-15  1.51e-08     0s
  16   2.01386970e+01  2.01386966e+01  0.00e+00 1.78e-15  2.14e-09     0s

Barrier solved model in 16 iterations and 0.02 seconds
Optimal objective 2.01386970e+01

Fixed MIQCP status(2): Model was solved to optimality (subject to tolerances).

MIQCP Solution:         20.138697    (377 iterations, 0 nodes)
Final Solve:            20.138697    (0 iterations)

Best possible:          20.138697
Absolute gap:            0.000000
Relative gap:            0.000000

This looks all fine. Except the correct (global) optimal objective is 2.2388. The reason is: this MIQCP model is actually non-convex. Gurobi usually rejects those models (with a message about a Q matrix not being positive definite) but in this case it slips through. The solution is probably just a local optimum.