When running SCIP-Jack (The STP application) on a particular Steiner Arborescence problem instance, the output logfile does not contain a valid solution when the stp/reduction setting is 1 or 2.
I'm wondering whether my file is not formatted correctly, whether my graph contains errors or whether the reductions are not applied correctly.
My graph was constructed in python using NetworkX. I check whether each edge is reachable from the root node and always give both the arc and anti-parallel arc a weight. The problem type is also set to "SAP". Most of the edges are bi-directional, and thus have the same weight in both directions.
My input file is as follows
33D32945 STP File, STP Format Version 1.0
SECTION Comment
Problem "SAP"
END
SECTION Graph
Nodes 49
Edges 62
A 23 47 289.36 10000000000
A 27 44 297.37 10000000000
A 29 46 295.36 10000000000
A 32 48 294.02 10000000000
A 34 45 295.66 10000000000
A 1 2 0.0 0.0
A 1 6 0.0 0.0
A 2 37 12.24 12.24
A 2 38 4.82 4.82
A 3 4 0.0 0.0
A 3 5 0.0 0.0
A 3 22 382.56 382.56
A 3 41 367.16 367.16
A 3 42 15.51 15.51
A 5 6 0.0 0.0
A 5 37 274.53 274.53
A 5 41 176.09 176.09
A 5 49 0 0
A 7 8 338.24 338.24
A 7 9 65.86 65.86
A 7 43 97.23 97.23
A 8 40 46.79 46.79
A 9 10 573.38 573.38
A 10 11 162.1 162.1
A 11 12 729.19 729.19
A 12 13 3.23 3.23
A 13 14 136.91 136.91
A 13 28 818.47 818.47
A 14 15 184.65 184.65
A 15 16 2.03 2.03
A 15 30 818.4 818.4
A 16 17 20.2 20.2
A 17 18 2023.02 2023.02
A 17 31 818.4 818.4
A 18 19 1465.78 1465.78
A 18 33 817.96 817.96
A 19 20 3.54 3.54
A 20 21 13.11 13.11
A 20 35 817.71 817.71
A 21 22 3.55 3.55
A 22 36 817.7 817.7
A 23 24 452.58 452.58
A 23 25 96.21 96.21
A 25 26 319.98 319.98
A 25 40 779.27 779.27
A 26 27 709.62 709.62
A 26 43 726.02 726.02
A 27 28 852.76 852.76
A 28 29 328.06 328.06
A 29 30 30.42 30.42
A 30 31 40.42 40.42
A 31 32 1280.36 1280.36
A 32 33 742.84 742.84
A 33 34 482.5 482.5
A 34 35 986.65 986.65
A 35 36 16.66 16.66
A 36 37 398.31 398.31
A 38 39 3.14 3.14
A 38 41 450.94 450.94
A 40 43 342.61 342.61
A 41 42 366.82 366.82
END
SECTION Terminals
Terminals 6
Root 49
T 44
T 45
T 46
T 47
T 48
T 49
END
EOF
I would expect the solution to have at least 10 edges, to connect everything. However, the reported solution is as follows (with stp/reduction=2).
SECTION Finalsolution
Vertices 2
V 5
V 49
Edges 1
E 5 49
End
The behaviour is caused by a bug in SCIP-Jack; SCIP-Jack is not very well tested for SAP unfortunately (due to a lack of test instances). It will be fixed as part of the next bugfix release. Please contact me (Daniel Rehfeldt) if you want to have a fixed version already.