Wednesday, November 21, 2012

1 vs 4 threads

Running a small MIP using 1 thread:

Optimize a model with 177 rows, 549 columns and 3800 nonzeros
Presolve time: 0.02s
Presolved: 177 rows, 549 columns, 3944 nonzeros
Variable types: 1 continuous, 548 integer (496 binary)
Found heuristic solution: objective 949.0000000

Root relaxation: objective 4.990000e+02, 947 iterations, 0.03 seconds

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

     0     0  499.00000    0   63  949.00000  499.00000  47.4%     -    0s
     0     0  499.00000    0   93  949.00000  499.00000  47.4%     -    0s
     0     0  499.00000    0   63  949.00000  499.00000  47.4%     -    0s
     0     2  499.00000    0   63  949.00000  499.00000  47.4%     -    0s
H  135   117                     910.0000000  499.00000  45.2%  47.3    0s
*  204    96              44     901.0000000  499.00000  44.6%  47.1    0s
  1963   797  891.00000   34   53  901.00000  578.12129  35.8%  46.1    5s
  6122  2135  822.02658   39   78  901.00000  720.84013  20.0%  34.5   10s
 12502  3801     cutoff   44       901.00000  796.00000  11.7%  27.4   15s
 21404  5575  891.00000   51   42  901.00000  862.00000  4.33%  21.7   20s
 34494  6391  891.00000   42   53  901.00000  891.00000  1.11%  17.1   25s
 52100  4430  891.00000   67   60  901.00000  891.00000  1.11%  12.8   31s
 68445  3439     cutoff   72       901.00000  891.00000  1.11%  10.7   35s
 94101  2702 infeasible   56       901.00000  891.00000  1.11%   8.9   40s
115791  2055     cutoff   55       901.00000  891.00000  1.11%   8.0   45s
141811  1165  891.00000   40   81  901.00000  891.00000  1.11%   7.2   50s
168722   165  891.00000   44   59  901.00000  891.00000  1.11%   6.7   55s

Explored 177443 nodes (1164346 simplex iterations) in 56.54 seconds
Thread count was 1 (of 8 available processors)

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

Now solve the same model with the same solver on the same machine using 4 threads:

Optimize a model with 177 rows, 549 columns and 3800 nonzeros
Presolve time: 0.02s
Presolved: 177 rows, 549 columns, 3944 nonzeros
Variable types: 1 continuous, 548 integer (496 binary)
Found heuristic solution: objective 949.0000000

Root relaxation: objective 4.990000e+02, 947 iterations, 0.03 seconds

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

     0     0  499.00000    0   63  949.00000  499.00000  47.4%     -    0s
     0     0  499.00000    0   93  949.00000  499.00000  47.4%     -    0s
     0     0  499.00000    0   63  949.00000  499.00000  47.4%     -    0s
     0     3  499.00000    0   63  949.00000  499.00000  47.4%     -    0s
*  141    97              50     901.0000000  499.00000  44.6%  50.9    0s
  6876  3503     cutoff   64       901.00000  558.96236  38.0%  30.4    5s
 31149  7878 infeasible   58       901.00000  891.00000  1.11%  18.1   10s
 72874  4957     cutoff   63       901.00000  891.00000  1.11%  12.2   18s
 87864  4665  891.00000   55    8  901.00000  891.00000  1.11%  11.3   20s

. . . .
97009933 49020  897.00000   80   47  901.00000  897.00000  0.44%   5.8 9085s
97054184 47405 infeasible   86       901.00000  897.00000  0.44%   5.8 9090s
97103347 45433 infeasible   95       901.00000  897.00000  0.44%   5.8 9095s
97174397    76 infeasible   97       901.00000  900.91810  0.01%   5.8 9100s

Explored 97174474 nodes (560614904 simplex iterations) in 9100.06 seconds
Thread count was 4 (of 8 available processors)

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

Solution times go from 1 minute to 2.5 hours! Extrapolating this to 8 cores gives me the shivers….