Performance of branching-imitation/example.ipynb

[ZedongPeng]

I am running the branching-imitation/example.ipynb . I didn't change any part of the code. However, the performance of the learned branching strategy on my computer is not as good as shown in example.ipynb on Github.

Is there any suggestion to improve the performance of the learned branching strategy?

The output of my local test is as follows.

• Output - Train a GNN

Epoch 1
Train loss: 4.031, accuracy 0.255
Valid loss: 3.684, accuracy 0.445
Epoch 2
Train loss: 3.507, accuracy 0.424
Valid loss: 3.385, accuracy 0.485
Epoch 3
Train loss: 3.461, accuracy 0.439
Valid loss: 3.398, accuracy 0.485
Epoch 4
Train loss: 3.430, accuracy 0.449
Valid loss: 3.378, accuracy 0.490
Epoch 5
Train loss: 3.383, accuracy 0.458
Valid loss: 3.392, accuracy 0.475
Epoch 6
Train loss: 3.394, accuracy 0.455
Valid loss: 3.394, accuracy 0.530
Epoch 7
Train loss: 3.403, accuracy 0.455
Valid loss: 3.369, accuracy 0.500
Epoch 8
Train loss: 3.385, accuracy 0.464
Valid loss: 3.379, accuracy 0.500
Epoch 9
Train loss: 3.390, accuracy 0.470
Valid loss: 3.379, accuracy 0.455
Epoch 10
Train loss: 3.368, accuracy 0.459
Valid loss: 3.367, accuracy 0.480
Epoch 11
Train loss: 3.377, accuracy 0.463
Valid loss: 3.388, accuracy 0.510
Epoch 12
Train loss: 3.374, accuracy 0.468
Valid loss: 3.365, accuracy 0.490
Epoch 13
Train loss: 3.377, accuracy 0.470
Valid loss: 3.354, accuracy 0.490
Epoch 14
Train loss: 3.363, accuracy 0.472
Valid loss: 3.493, accuracy 0.515
Epoch 15
Train loss: 3.370, accuracy 0.460
Valid loss: 3.328, accuracy 0.495
Epoch 16
Train loss: 3.397, accuracy 0.454
Valid loss: 3.438, accuracy 0.490
Epoch 17
Train loss: 3.372, accuracy 0.461
Valid loss: 3.368, accuracy 0.495
Epoch 18
Train loss: 3.346, accuracy 0.456
Valid loss: 3.334, accuracy 0.475
Epoch 19
Train loss: 3.343, accuracy 0.466
Valid loss: 3.317, accuracy 0.470
Epoch 20
Train loss: 3.362, accuracy 0.450
Valid loss: 3.387, accuracy 0.495
Epoch 21
Train loss: 3.340, accuracy 0.463
Valid loss: 3.320, accuracy 0.490
Epoch 22
Train loss: 3.329, accuracy 0.465
Valid loss: 3.342, accuracy 0.475
Epoch 23
Train loss: 3.329, accuracy 0.456
Valid loss: 3.359, accuracy 0.500
Epoch 24
Train loss: 3.324, accuracy 0.450
Valid loss: 3.380, accuracy 0.480
Epoch 25
Train loss: 3.315, accuracy 0.455
Valid loss: 3.315, accuracy 0.500
Epoch 26
Train loss: 3.309, accuracy 0.466
Valid loss: 3.285, accuracy 0.485
Epoch 27
Train loss: 3.302, accuracy 0.465
Valid loss: 3.263, accuracy 0.485
Epoch 28
Train loss: 3.231, accuracy 0.475
Valid loss: 3.280, accuracy 0.480
Epoch 29
Train loss: 3.241, accuracy 0.454
Valid loss: 3.204, accuracy 0.485
Epoch 30
Train loss: 3.216, accuracy 0.472
Valid loss: 3.330, accuracy 0.445
Epoch 31
Train loss: 3.176, accuracy 0.472
Valid loss: 3.188, accuracy 0.455
Epoch 32
Train loss: 3.168, accuracy 0.471
Valid loss: 3.193, accuracy 0.470
Epoch 33
Train loss: 3.188, accuracy 0.468
Valid loss: 3.278, accuracy 0.495
Epoch 34
Train loss: 3.214, accuracy 0.465
Valid loss: 3.198, accuracy 0.500
Epoch 35
Train loss: 3.191, accuracy 0.468
Valid loss: 3.191, accuracy 0.500
Epoch 36
Train loss: 3.155, accuracy 0.465
Valid loss: 3.137, accuracy 0.475
Epoch 37
Train loss: 3.142, accuracy 0.465
Valid loss: 3.163, accuracy 0.455
Epoch 38
Train loss: 3.093, accuracy 0.474
Valid loss: 3.127, accuracy 0.495
Epoch 39
Train loss: 3.128, accuracy 0.481
Valid loss: 3.123, accuracy 0.540
Epoch 40
Train loss: 3.060, accuracy 0.484
Valid loss: 3.236, accuracy 0.460
Epoch 41
Train loss: 3.110, accuracy 0.474
Valid loss: 3.094, accuracy 0.525
Epoch 42
Train loss: 3.061, accuracy 0.492
Valid loss: 3.165, accuracy 0.500
Epoch 43
Train loss: 3.054, accuracy 0.500
Valid loss: 3.131, accuracy 0.490
Epoch 44
Train loss: 3.030, accuracy 0.497
Valid loss: 3.182, accuracy 0.480
Epoch 45
Train loss: 3.026, accuracy 0.500
Valid loss: 3.204, accuracy 0.450
Epoch 46
Train loss: 3.010, accuracy 0.490
Valid loss: 3.125, accuracy 0.480
Epoch 47
Train loss: 3.009, accuracy 0.515
Valid loss: 3.159, accuracy 0.450
Epoch 48
Train loss: 3.065, accuracy 0.494
Valid loss: 3.305, accuracy 0.430
Epoch 49
Train loss: 3.044, accuracy 0.494
Valid loss: 3.168, accuracy 0.465
Epoch 50
Train loss: 3.023, accuracy 0.504
Valid loss: 3.187, accuracy 0.455

• action_distribution

tensor([0.0140, 0.0140, 0.0142, 0.0141, 0.0140, 0.0141, 0.0142, 0.0140, 0.0140,
        0.0141, 0.0142, 0.0142, 0.0141, 0.0140, 0.0140, 0.0141, 0.0140, 0.0141,
        0.0142, 0.0139, 0.0141, 0.0141, 0.0142, 0.0140, 0.0141, 0.0142, 0.0140,
        0.0140, 0.0141, 0.0140, 0.0142, 0.0142, 0.0142, 0.0141, 0.0141, 0.0141,
        0.0140, 0.0141, 0.0139, 0.0142, 0.0142, 0.0141, 0.0139, 0.0139, 0.0142,
        0.0142, 0.0140, 0.0141, 0.0142, 0.0140, 0.0141, 0.0139, 0.0140, 0.0139,
        0.0140, 0.0142, 0.0140, 0.0141, 0.0140, 0.0142, 0.0140, 0.0142, 0.0141,
        0.0142, 0.0139, 0.0141, 0.0140, 0.0142, 0.0140, 0.0143, 0.0142],
       grad_fn=<SoftmaxBackward0>)

• Evaluation

Instance   0 | SCIP nb nodes      34  | SCIP time     5.79 
             | GNN  nb nodes     211  | GNN  time    11.62 
             | Gain          -520.59% | Gain       -100.94%
Instance   1 | SCIP nb nodes       5  | SCIP time     2.00 
             | GNN  nb nodes      24  | GNN  time     2.54 
             | Gain          -380.00% | Gain        -26.92%
Instance   2 | SCIP nb nodes       3  | SCIP time     1.75 
             | GNN  nb nodes      41  | GNN  time     2.61 
             | Gain         -1266.67% | Gain        -49.45%
Instance   3 | SCIP nb nodes       1  | SCIP time     0.14 
             | GNN  nb nodes       1  | GNN  time     0.19 
             | Gain             0.00% | Gain        -31.89%
Instance   4 | SCIP nb nodes     168  | SCIP time     5.31 
             | GNN  nb nodes     315  | GNN  time    19.34 
             | Gain           -87.50% | Gain       -263.96%
Instance   5 | SCIP nb nodes       5  | SCIP time     2.87 
             | GNN  nb nodes      51  | GNN  time     4.46 
             | Gain          -920.00% | Gain        -55.82%
Instance   6 | SCIP nb nodes      81  | SCIP time     4.41 
             | GNN  nb nodes     271  | GNN  time    12.80 
             | Gain          -234.57% | Gain       -190.05%
Instance   7 | SCIP nb nodes       1  | SCIP time     1.48 
             | GNN  nb nodes       1  | GNN  time     1.91 
             | Gain             0.00% | Gain        -29.66%
Instance   8 | SCIP nb nodes      13  | SCIP time     2.29 
             | GNN  nb nodes      83  | GNN  time     4.52 
             | Gain          -538.46% | Gain        -97.48%
Instance   9 | SCIP nb nodes       3  | SCIP time     1.64 
             | GNN  nb nodes      29  | GNN  time     1.86 
             | Gain          -866.67% | Gain        -12.90%
Instance  10 | SCIP nb nodes       3  | SCIP time     1.64 
             | GNN  nb nodes      23  | GNN  time     2.05 
             | Gain          -666.67% | Gain        -25.21%
Instance  11 | SCIP nb nodes       1  | SCIP time     2.07 
             | GNN  nb nodes      19  | GNN  time     2.27 
             | Gain         -1800.00% | Gain         -9.59%
Instance  12 | SCIP nb nodes       3  | SCIP time     2.28 
             | GNN  nb nodes      27  | GNN  time     2.94 
             | Gain          -800.00% | Gain        -29.21%
Instance  13 | SCIP nb nodes       9  | SCIP time     2.32 
             | GNN  nb nodes      93  | GNN  time     4.17 
             | Gain          -933.33% | Gain        -79.56%
Instance  14 | SCIP nb nodes      11  | SCIP time     2.53 
             | GNN  nb nodes      57  | GNN  time     3.78 
             | Gain          -418.18% | Gain        -49.28%
Instance  15 | SCIP nb nodes      11  | SCIP time     3.99 
             | GNN  nb nodes      65  | GNN  time     6.73 
             | Gain          -490.91% | Gain        -68.68%
Instance  16 | SCIP nb nodes      15  | SCIP time     3.75 
             | GNN  nb nodes     139  | GNN  time     8.29 
             | Gain          -826.67% | Gain       -121.08%
Instance  17 | SCIP nb nodes       3  | SCIP time     1.79 
             | GNN  nb nodes      19  | GNN  time     1.68 
             | Gain          -533.33% | Gain          5.98%
Instance  18 | SCIP nb nodes       1  | SCIP time     2.22 
             | GNN  nb nodes      19  | GNN  time     2.26 
             | Gain         -1800.00% | Gain         -2.14%
Instance  19 | SCIP nb nodes      11  | SCIP time     3.04 
             | GNN  nb nodes      53  | GNN  time     4.26 
             | Gain          -381.82% | Gain        -40.10%

• Evaluation on larger and harder instances

Instance   0 | SCIP nb nodes       9  | SCIP time     5.09 
             | GNN  nb nodes     105  | GNN  time     9.20 
             | Gain         -1066.67% | Gain        -80.92%
Instance   1 | SCIP nb nodes       5  | SCIP time     3.56 
             | GNN  nb nodes      83  | GNN  time     5.56 
             | Gain         -1560.00% | Gain        -56.40%
Instance   2 | SCIP nb nodes       5  | SCIP time     1.72 
             | GNN  nb nodes      41  | GNN  time     2.30 
             | Gain          -720.00% | Gain        -33.71%
Instance   3 | SCIP nb nodes      13  | SCIP time     3.15 
             | GNN  nb nodes      81  | GNN  time     5.49 
             | Gain          -523.08% | Gain        -74.06%
Instance   4 | SCIP nb nodes       3  | SCIP time     2.26 
             | GNN  nb nodes      27  | GNN  time     2.85 
             | Gain          -800.00% | Gain        -26.00%
Instance   5 | SCIP nb nodes      19  | SCIP time     2.80 
             | GNN  nb nodes     159  | GNN  time     7.13 
             | Gain          -736.84% | Gain       -155.07%
Instance   6 | SCIP nb nodes       3  | SCIP time     1.54 
             | GNN  nb nodes       5  | GNN  time     1.47 
             | Gain           -66.67% | Gain          4.52%
Instance   7 | SCIP nb nodes      35  | SCIP time     5.22 
             | GNN  nb nodes     250  | GNN  time    14.95 
             | Gain          -614.29% | Gain       -186.62%
Instance   8 | SCIP nb nodes      47  | SCIP time     5.07 
             | GNN  nb nodes     323  | GNN  time    18.48 
             | Gain          -587.23% | Gain       -264.32%
Instance   9 | SCIP nb nodes      52  | SCIP time     5.14 
             | GNN  nb nodes     167  | GNN  time    11.72 
             | Gain          -221.15% | Gain       -128.19%
Instance  10 | SCIP nb nodes       3  | SCIP time     2.61 
             | GNN  nb nodes      21  | GNN  time     2.27 
             | Gain          -600.00% | Gain         13.13%
Instance  11 | SCIP nb nodes       1  | SCIP time     0.43 
             | GNN  nb nodes       1  | GNN  time     0.30 
             | Gain             0.00% | Gain         28.67%
Instance  12 | SCIP nb nodes       5  | SCIP time     2.55 
             | GNN  nb nodes      25  | GNN  time     2.80 
             | Gain          -400.00% | Gain         -9.73%
Instance  13 | SCIP nb nodes       5  | SCIP time     2.24 
             | GNN  nb nodes      35  | GNN  time     2.71 
             | Gain          -600.00% | Gain        -21.21%
Instance  14 | SCIP nb nodes       3  | SCIP time     2.37 
             | GNN  nb nodes      45  | GNN  time     3.56 
             | Gain         -1400.00% | Gain        -50.26%
Instance  15 | SCIP nb nodes      17  | SCIP time     4.24 
             | GNN  nb nodes     141  | GNN  time    10.36 
             | Gain          -729.41% | Gain       -144.38%
Instance  16 | SCIP nb nodes       3  | SCIP time     1.44 
             | GNN  nb nodes      18  | GNN  time     1.61 
             | Gain          -500.00% | Gain        -11.54%
Instance  17 | SCIP nb nodes       1  | SCIP time     0.29 
             | GNN  nb nodes       1  | GNN  time     0.29 
             | Gain             0.00% | Gain         -0.71%
Instance  18 | SCIP nb nodes       5  | SCIP time     3.25 
             | GNN  nb nodes      31  | GNN  time     3.93 
             | Gain          -520.00% | Gain        -21.11%
Instance  19 | SCIP nb nodes     101  | SCIP time     4.43 
             | GNN  nb nodes     359  | GNN  time    22.54 
             | Gain          -255.45% | Gain       -408.47%

[Ljj199807]

I also encountered the same problem as you in practice, did you solve this problem?

[ZedongPeng]

Nope. I didn't resolve it.

[Ljj199807]

According to the literature [1], I added a parameter initialization, which can indeed achieve a certain acceleration effect on the GPU. But I'm not sure if I used the GPU to get the acceleration or if I added the "Prenorm layers" in [1]. Because according to the author's follow-up article, this model does not work well directly on the CPU[2].
[1]Exact combinatorial optimization with graph convolutional neural networks
[2]Hybrid Models for Learning to Branch