Friday, April 24, 2015

MIQP bounds and performance

Cplex automatic reformulations

The performance of MIQP models is not always predictable. Here are the results for a small model we used to reproduce a performance issue with Cplex:

image

Looks like Cplex is attempting a smart reformulation that fails terribly. An indication is the log line:

Reduced MIQP objective Q matrix has 1 nonzeros.

Also the negative best bound (compare this to the relaxed objective) is an indication.

There are two ways to fix the problem. A small reformulation that simplifies the objective, leads to much better performance:

image  

In this case the objective is written as a sum of squares of continuous variables, and this prohibits Cplex to do their reformulations. The second way is to use option qtolin and set it to zero.

image

See: http://www-01.ibm.com/support/knowledgecenter/SSSA5P_12.6.1/ilog.odms.cplex.help/CPLEX/Parameters/topics/QToLin.html?lang=en.

The same issue is discussed in:

With a slight variation of this model we can make Mosek look bad. This variant of the model can be easily linearized, which helps tremendously in this case.

image

The linearized model solves very easily, although there are some bugs with reporting the correct gap. This gap should be 0%, but instead we see:

Best possible: +inf
Absolute gap:       3.000000E+300
Relative gap:            1.000000

This could be related to the relaxed LP having integer values.

Tuesday, April 21, 2015

Scary numbers

In http://lists.gnu.org/archive/html/help-glpk/2015-04/msg00031.html we see GLPK failing with some scary looking messages:

With glpk 4.52 and with the attached input, I get the following failure/error:

------------------------------------------------------------------------------
$ glpsol --lp mi.cplex

Warning: numerical instability (primal simplex, phase I)
   2979: obj =   1.092652474e+04  infeas =  5.265e+09 (0)
Warning: numerical instability (primal simplex, phase I)
   2996: obj =   1.092637382e+04  infeas =  5.260e+09 (0)
   3000: obj =   1.092644011e+04  infeas =  5.235e+09 (0)
Warning: numerical instability (primal simplex, phase I)
   3051: obj =   1.077725595e+04  infeas =  5.201e+09 (0)
Warning: numerical instability (primal simplex, phase I)
   3059: obj =   1.074805814e+04  infeas =  5.185e+09 (0)
Warning: numerical instability (primal simplex, phase I)
   3122: obj =   1.998434476e+03  infeas =  3.955e+05 (0)
Warning: numerical instability (primal simplex, phase I)
   3159: obj =   1.998431624e+03  infeas =  3.944e+05 (0)
Error: unable to factorize the basis matrix (1)
Sorry, basis recovery procedure not implemented yet
glp_intopt: cannot solve LP relaxation
Time used:   1.7 secs
Memory used: 10.8 Mb (11322915 bytes)
--------------------------------------------------------------

Any insights/workarounds will be appreciated.

Even more scary is the following part of the log:

Scaling...
A: min|aij| =  1.000e+00  max|aij| =  2.306e+18  ratio =  2.306e+18
GM: min|aij| =  1.213e-04  max|aij| =  8.246e+03  ratio =  6.800e+07
EQ: min|aij| =  1.480e-08  max|aij| =  1.000e+00  ratio =  6.755e+07
2N: min|aij| =  1.490e-08  max|aij| =  1.500e+00  ratio =  1.007e+08
Commercial solvers typically do much better on these kind of poorly scaled models. As the attached problem file was called mi.cplex, I tried Cplex’s DropSolve on-line tool on this problem. It solves it quickly:

Changed parameter CPX_PARAM_THREADS from 0 to 12
Param[1,067] = 12
Param[1,130] = UTF-8
Param[1,132] = -1
Tried aggregator 1 time.
MIP Presolve eliminated 535 rows and 0 columns.
MIP Presolve modified 38 coefficients.
Reduced MIP has 4312 rows, 345 columns, and 48488 nonzeros.
Reduced MIP has 152 binaries, 193 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (16.48 ticks)
Found incumbent of value 1.2193885e+12 after 0.05 sec. (30.35 ticks)
Probing time = 0.11 sec. (6.03 ticks)
Tried aggregator 1 time.
Reduced MIP has 4312 rows, 345 columns, and 48488 nonzeros.
Reduced MIP has 152 binaries, 193 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.01 sec. (11.80 ticks)
Probing time = 0.11 sec. (5.81 ticks)
Clique table members: 744.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 12 threads.
Root relaxation solution time = 0.08 sec. (17.25 ticks)

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

*     0+    0                       1.21939e+12     -228.0000           100.00%
*     0+    0                       1.21939e+12     -228.0000           100.00%
*     0+    0                       1.21939e+12     -228.0000           100.00%
      0     0        0.0000    76   1.21939e+12        0.0000      190  100.00%
      0     0       22.2000   114   1.21939e+12     Fract: 76      663  100.00%
*     0+    0                       6.45608e+11       22.2000           100.00%
      0     2       22.2000   114   6.45608e+11       22.2000      663  100.00%
Elapsed time = 1.08 sec. (582.03 ticks, tree = 0.00 MB, solutions = 4)
*     3+    3                       137054.0000       23.0197            99.98%
      3     5      820.0414   170   137054.0000       23.0197     2837   99.98%
     13    15      963.0516   223   137054.0000      822.1327     5049   99.40%
*   156   119      integral     0     4281.0000      822.1327    12517   80.80%
    160    65     4266.0500   109     4281.0000      858.1613    12976   79.95%
*   197    31      integral     0     4278.0000      858.1613    13771   79.94%
*   207    21      integral     0     4275.0000      858.1613    13951   79.93%

Gomory fractional cuts applied:  76

Root node processing (before b&c):
  Real time             =    1.06 sec. (578.93 ticks)
Parallel b&c, 12 threads:
  Real time             =    1.62 sec. (1062.86 ticks)
  Sync time (average)   =    1.06 sec.
  Wait time (average)   =    1.10 sec.
                          ------------
Total (root+branch&cut) =    2.67 sec. (1641.79 ticks)
Incumbent solution:
MILP objective                                 4.2750000000e+03
MILP solution norm |x| (Total, Max)            1.36000e+02  6.00000e+00
MILP solution error (Ax=b) (Total, Max)        2.02749e-12  1.13687e-13
MILP x bound error (Total, Max)                3.15081e-13  1.05027e-13
MILP x integrality error (Total, Max)          1.22169e-12  2.08722e-13
MILP slack bound error (Total, Max)            7.46694e-11  1.98952e-12
integer optimal solution (101)

I would certainly double check the solution.

Note: The first run on DropSolve failed. I renamed the file (not sure if the filename contributed to the problem), and tried again. Now it worked:

image

Friday, April 17, 2015

Margin vs Mark Up

See e.g. http://en.wikipedia.org/wiki/Gross_margin

The definitions are:

image

Often these terms are used in a less precise manner.

Does not happen a lot

Often Gurobi and Cplex are in the same ballpark when solving my models. But sometimes you can see something like this:

image

The model is related to scheduling maintenance for power generators.

Note: I also have seen cases the other way around (Gurobi much faster than Cplex).

Wednesday, April 15, 2015

operating on an empty set

See: http://www.johndcook.com/blog/2015/04/14/empty-sum-product/

image

Of course modeling systems should do this correctly.

GAMS

$onempty;
set e(*) / /;
display e;

scalars s,p;
s =
sum(e,1);
p =
prod(e,1);
display s,p;

Gives:

----      3 SET e 

                                                      ( EMPTY )

----      8 PARAMETER s                    =        0.000 
            PARAMETER p                    =        1.000
 

AMPL

ampl: set e = {};
ampl: param s = sum{i in e} 1;
ampl: param p = prod{i in e} 1;
ampl: display s,p;
s = 0
p = 1

Thursday, April 2, 2015

Diagonalization Algorithm

Following

image

we can write a simple diagonalization / relaxation algorithm in GAMS that computes the oligopolistic market equilibrium of the problem described here: http://yetanothermathprogrammingconsultant.blogspot.com/2015/03/oligopolistic-producer-behavior-or-why.html.

In this algorithm we solve a sub-problem where we maximize profits (varying the output) for each firm while we keep the output of the other firms constant in the sub-problem (i.e. we take them from the previous iteration of the algorithm). The sub-problem is now a straightforward NLP. It looks like:

image

We run this model in a loop until it converges: the quantities produced don’t change anymore:

 image

We see we can reproduce the results from the paper:

image

----    104 PARAMETER trace 

             firm1       firm2       firm3       firm4       firm5        diff

iter0       10.000      10.000      10.000      10.000      10.000
iter1       55.029      56.193      55.760      53.414      49.142     219.538
iter2       27.188      32.991      36.158      36.505      34.382     102.314
iter3       42.618      46.760      48.008      46.372      42.300      58.834
iter4       33.565      38.853      41.170      40.545      37.475      34.451
iter5       38.886      43.533      45.192      43.922      40.220      20.146
iter6       35.778      40.804      42.835      41.927      38.583      11.827
iter7       37.607      42.411      44.218      43.092      39.534       6.935
iter8       36.536      41.470      43.406      42.406      38.972       4.071
iter9       37.165      42.022      43.883      42.808      39.301       2.388
iter10      36.796      41.698      43.603      42.572      39.108       1.402
iter11      37.013      41.888      43.767      42.710      39.221       0.822
iter12      36.886      41.777      43.671      42.629      39.154       0.483
iter13      36.960      41.842      43.727      42.677      39.193       0.283
iter14      36.916      41.804      43.694      42.649      39.170       0.166
iter15      36.942      41.826      43.714      42.665      39.184       0.098
iter16      36.927      41.813      43.702      42.656      39.176       0.057
iter17      36.936      41.821      43.709      42.661      39.181       0.034
iter18      36.931      41.816      43.705      42.658      39.178       0.020
iter19      36.934      41.819      43.707      42.660      39.180       0.012
iter20      36.932      41.818      43.706      42.659      39.179       0.007

It is always nice to see that we can reproduce some results.

Notes:

  • Note: to speed up the iterations we can set solprint and solvelink:
    image 
  • Patrick Harker has been appointed as the next president of the Fed in Philadelphia [link].
  • The trace output illustrates the linear convergence of this algorithm: the difference is halved by each iteration.
  • This algorithm is also known as the PIES-q algorithm [link].

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.

Interesting Xpress log

On a very small (convex) MIQCP model (it solves within the limits of the demo version of GAMS/Xpress) we see Xpress struggling mightily. Commercial solvers like Xpress are very robust for LP and MIP models, but they seem somewhat less reliable with respect to quadratic models, probably because they are less exposed to quadratic models.

MODEL STATISTICS

BLOCKS OF EQUATIONS          51    SINGLE EQUATIONS           51
BLOCKS OF VARIABLES          89    SINGLE VARIABLES           89
NON ZERO ELEMENTS           241     NON LINEAR N-Z             80
DERIVATIVE POOL              20     CONSTANT POOL              36
CODE LENGTH                 400     DISCRETE VARIABLES         40

FICO-Xpress      24.4.1 r50296 Released Dec 20, 2014 WEI x86 64bit/MS Windows

Xpress Optimizer 27.01
Xpress-Optimizer 64-bit v27.01.02 (Hyper capacity)
(c) Copyright Fair Isaac Corporation 1983-2014. All rights reserved
Licensed for use by: GAMS Development Corp. for GAMS

Reading Problem m
Problem Statistics
          50 (      0 spare) rows
          88 (      0 spare) structural columns
         200 (      0 spare) non-zero elements
          80 quadratic elements in 40 quadratic constraints
Global Statistics
          40 entities        0 sets        0 set members
Minimizing MIQCQP m
Original problem has:
        50 rows           88 cols          200 elements        40 globals
        40 qrows          80 qrowelem
Presolved problem has:
        50 rows           88 cols          200 elements        40 globals
        40 qrows          80 qrowelem
Will try to keep branch and bound tree memory usage below 21.7Gb
Barrier cache sizes : L1=32K L2=8192K
Using AVX support
Cores per CPU (CORESPERCPU): 8
Barrier starts, with L2 cache 1024K
Matrix ordering - Dense cols.:      0   NZ(L):       950   Flops:        14984
  Its   P.inf      D.inf      U.inf      Primal obj.     Dual obj.      Compl.
   0  1.91e+001  1.19e+001  9.70e+000  2.8159564e+003 -2.6134886e+002  3.8e+003
   1  7.49e+000  5.91e+000  1.54e+000  5.8570174e+002 -8.3787742e+001  7.2e+002
   2  1.28e+000  3.28e-001  1.10e-002  2.9030624e+000 -1.2271889e+001  1.9e+001
   3  9.84e-002  1.92e-002  8.10e-004  1.6036787e-001 -1.0029935e+000  2.0e+000
   4  7.98e-004  3.67e-003  5.07e-006  1.9140695e-003 -7.4258213e-003  2.5e-002
   5  2.11e-006  1.03e-005  1.33e-008  5.1448073e-006 -1.5450951e-005  6.0e-005
   6  2.13e-009  1.05e-008  1.34e-011  5.2140230e-009 -1.5655265e-008  6.1e-008
Barrier method finished in 0 seconds
Crossover starts

   Its         Obj Value      S   Ninf  Nneg        Sum Inf  Time
    42           .000000      P     45     0     416.304867     0
     0           .000000      N     45     0     416.304867     0
     0           .000000      D     45     0        .000000     0
Crossover successful
Objective function value:      .000000 time: 0
     0           .000000      P     12    36       6.913862     0
    14           .000000      P      0     0        .000000     0
Optimal solution found
Barrier solved problem
  6 barrier and 56 simplex iterations in 0s

Final objective                         : 0.000000000000000e-01
  Max primal violation      (abs / rel) :       0.0 /       0.0
  Max dual violation        (abs / rel) :       0.0 /       0.0
  Max complementarity viol. (abs / rel) :       0.0 /       0.0
All values within tolerances

Starting root cutting & heuristics

Its Type    BestSoln    BestBound   Sols    Add    Del     Gap     GInf   Time
+           75.710978      .000000      1               75.7110        0      0
+           75.297982      .000000      2               75.2980        0      0
   1  O     75.297982      .487605      2     50     20   99.35%      29      0
   2  O     75.297982    13.426199      2     51     48   82.17%      26      0
   3  O     75.297982    33.375760      2     38     25   55.68%      12      0
   4  O     75.297982    60.087607      2     52     40   20.20%      18      0
   5  O     75.297982    71.987890      2     34     40    4.40%      12      0
   6  O     75.297982    74.005329      2     30     24    1.72%       6      0
   7  K     75.297982    74.005329      2     13     23    1.72%      16      0
   8  K     75.297982    74.005329      2      5     15    1.72%      16      0
   9  K     75.297982    74.005329      2      7      5    1.72%      10      0
  10  K     75.297982    74.005329      2      0      7    1.72%      10      0
Heuristic search started
Heuristic search stopped

Cuts in the matrix         : 73
Cut elements in the matrix : 216
Its Type    BestSoln    BestBound   Sols    Add    Del     Gap     GInf   Time
   1  O     75.297982    74.005329      2     35      5    1.72%       0      0
   2  O     75.297982    74.005329      2     19     36    1.72%       0      0
   3  O     75.297982    74.005329      2     23     17    1.72%       0      0
Will try to keep branch and bound tree memory usage below 21.7Gb

Starting tree search

    Node     BestSoln    BestBound   Sols Active  Depth     Gap     GInf   Time
       1    75.297982    74.005329      2      2      1    1.72%      18      0
       2    75.297982    74.005329      2      1      2    1.72%      21      0
       3    75.297982    74.005329      2      2      3    1.72%      20      0
       4    75.297982    74.005329      2      3      4    1.72%      20      0
       5    75.297982    74.005329      2      4      5    1.72%      20      0
       6    75.297982    74.005329      2      5      6    1.72%      19      0
       7    75.297982    74.005381      2      6      3    1.72%      19      0
       8    75.297982    74.005383      2      7      7    1.72%      19      0
       9    75.297982    74.031433      2      8      5    1.68%      18      0
      10    75.297982    74.031433      2      9      6    1.68%      16      0
+     15    74.628262    74.031433      3     11     10    0.80%       0      0
+     19    74.628249    74.031433      4     11     14    0.80%       0      0
      20    74.628249    74.031433      4     11     14    0.80%       2      0
      30    74.628249    74.031433      4     18     14    0.80%       4      0
      40    74.628249    74.031449      4     25     11    0.80%       8      0
      50    74.628249    74.077101      4     31      8    0.74%      16      0
+     59    74.576175    74.077101      5     31     16    0.67%       0      0
      60    74.576175    74.077101      5     31     16    0.67%       2      0
+     60    74.525346    74.077101      6     31     17    0.60%       0      0
B&B tree size: 144k total

    Node     BestSoln    BestBound   Sols Active  Depth     Gap     GInf   Time
      70    74.525346    74.077154      6     36      6    0.60%      14      0
+     79    74.501844    74.077154      7     36     14    0.57%       0      0
      80    74.501844    74.077154      7     36     14    0.57%       2      0
+     80    74.451129    74.077154      8     36     15    0.50%       0      0
      90    74.451129    74.079222      8     39      4    0.50%      16      0
     100    74.451129    74.079222      8     45      4    0.50%      16      0
     200    74.451129    74.100052      8     89     14    0.47%       6      0
     300    74.451129    74.105467      8    134      9    0.46%      16      0
     400    74.451129    74.123164      8    161     14    0.44%       6      0
     500    74.451129    74.131429      8    185     11    0.43%       8      0
     600    74.451129    74.172380      8    207     16    0.37%       2      0
     700    74.451129    74.179219      8    245     10    0.37%       4      0
     800    74.451129    74.203200      8    265     13    0.33%       6      0
+    884    74.441499    74.205322      9    289     20    0.32%       0      0
     900    74.441499    74.205322      9    290     14    0.32%       8      0
    1000    74.441499    74.205322      9    311     11    0.32%       2      0
    1200    74.441499    74.205322      9    367     16    0.32%      12      0
+   1217    74.408242    74.205322     10    369     23    0.27%       0      0
    1300    74.408242    74.220873     10    352     17    0.25%       4      0
    1400    74.408242    74.231426     10    363     10    0.24%       8      0
B&B tree size: 1.0Mb total

    Node     BestSoln    BestBound   Sols Active  Depth     Gap     GInf   Time
    1500    74.408242    74.231426     10    382     16    0.24%       4      1
    1700    74.408242    74.250990     10    415     14    0.21%       8      1
    1800    74.408242    74.257529     10    439     15    0.20%       6      1
+   1818    74.408060    74.257529     11    436     20    0.20%       0      1
    1900    74.408060    74.261403     11    443     17    0.20%       4      1
    2000    74.408060    74.271531     11    448     10    0.18%       7      1
    2100    74.408060    74.277093     11    451     11    0.18%       6      1
    2200    74.408060    74.279215     11    462     16    0.17%       4      1
    2300    74.408060    74.283948     11    468     13    0.17%       2      1
    2400    74.408060    74.287506     11    477     16    0.16%       4      1
    2500    74.408060    74.299222     11    468     11    0.15%       2      1
    2600    74.408060    74.305186     11    477      7    0.14%      10      1
    2700    74.408060    74.305319     11    485     14    0.14%       8      1
    2800    74.408060    74.305319     11    479     15    0.14%       4      1
    3000    74.408060    74.315007     11    449     16    0.13%       4      1
    3100    74.408060    74.327330     11    427     17    0.11%       4      2
    3200    74.408060    74.331422     11    420     15    0.10%       2      2
    3400    74.408060    74.342707     11    377     13    0.09%       8      2
    3500    74.408060    74.352660     11    363     15    0.07%       2      2
    3600    74.408060    74.359277     11    339     19    0.07%       4      2
B&B tree size: 1.3Mb total

    Node     BestSoln    BestBound   Sols Active  Depth     Gap     GInf   Time
    3700    74.408060    74.373115     11    303     13    0.05%       2      2
    3900    74.408060    74.379200     11    275     15    0.04%       4      2
    4000    74.408060    74.379212     11    258     14    0.04%       2      2
    4200    74.408060    74.387502     11    192     19    0.03%       5      2
    4500    74.408060    74.405315     11     59     15   0.004%       4      3
    4600    74.408060    74.405640     11     15     15   0.003%      10      3
*** Search completed ***     Time:     3 Nodes:       4629
Number of integer feasible solutions found is 11
Best integer solution found is    74.408060
Best bound is    74.408060
Warning: 6 node(s) could not be solved or branched. Final bound or status may be incorrect.

Uncrunching matrix
fixing discrete vars and re-solving as an LP.
Minimizing QCQP m
Original problem has:
        50 rows           88 cols          200 elements
        40 qrows          80 qrowelem
Presolved problem has:
        40 rows           48 cols          120 elements
        40 qrows          80 qrowelem
Barrier cache sizes : L1=32K L2=8192K
Using AVX support
Cores per CPU (CORESPERCPU): 8
Barrier starts, with L2 cache 1024K
Matrix ordering - Dense cols.:      0   NZ(L):       376   Flops:         2520
  Its   P.inf      D.inf      U.inf      Primal obj.     Dual obj.      Compl.
   0  1.83e+001  2.52e+001  1.16e+001  1.5112915e+003 -9.4937458e+002  2.6e+003
   1  4.74e+000  9.55e+000  1.19e+000  2.5408247e+002 -2.9217970e+002  3.9e+002
   2  2.34e+000  3.44e+000  3.35e-001  7.8404847e+001 -1.0977438e+002  1.4e+002
   3  7.92e-001  6.84e-001  1.89e-002  5.2158577e+000 -1.3750171e+001  1.4e+001
   4  6.28e-001  6.38e-001  1.33e-002  4.1020675e+000 -7.8600545e+000  1.1e+001
   5  4.37e-001  3.32e-001  8.43e-003  9.0795149e+000  3.4120483e-001  1.5e+001
   6  1.98e-001  2.61e-001  3.73e-003  9.3869573e+000  4.9561739e+000  8.6e+000
   7  3.63e-002  6.02e-002  3.74e-004  8.7705271e+000  7.9879673e+000  1.3e+000
   8  8.70e-003  2.50e-002  3.59e-005  8.6114463e+000  8.6224795e+000  1.4e-001
   9  2.28e-003  1.31e-002  4.91e-006  8.5979647e+000  8.6831580e+000  2.5e-002
  10  3.52e-004  2.47e-003  4.60e-009  8.5944005e+000  8.5952389e+000  2.2e-004
  11  5.07e-005  7.03e-004  6.92e-012  8.5943916e+000  8.5948297e+000  2.1e-005
  12  8.59e-006  2.20e-004  8.78e-016  8.5943913e+000  8.5944862e+000  2.5e-006
  13  1.56e-006  7.24e-005  8.78e-016  8.5943913e+000  8.5944094e+000  2.9e-007
  14  3.00e-007  2.42e-005  1.10e-015  8.5943913e+000  8.5943941e+000  3.3e-008
Barrier method finished in 0 seconds
Uncrunching matrix
Optimal solution found

   Its         Obj Value      S   Ninf  Nneg        Sum Inf  Time
     0          8.594391      B      0     0        .000000     0
Barrier solved problem
  14 barrier iterations in 0s

Final objective                         : 8.594391251039179e+00
  Max primal violation      (abs / rel) : 8.474e-07 / 5.042e-08
  Max dual violation        (abs / rel) :       0.0 /       0.0
  Max complementarity viol. (abs / rel) : 4.300e-07 / 1.758e-08
All values within tolerances

fixed LP solved successfully, objective = 8.59439125104.

Integer solution proven optimal.

MIP solution  :          8.594391
Best possible :         74.408060
Absolute gap  :        -65.813669     optca :          0.000000
Relative gap  :         -0.884497     optcr :          0.000000

The correct optimal objective is 0.8404.