Wednesday, April 1, 2015

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.

No comments:

Post a Comment