SCIP-Jack开启归约时输出无效Steiner Arborescence解决方案问询

I'm running into a problem with SCIP-Jack when solving a specific Steiner Arborescence (SAP) instance: when setting stp/reduction to 1 or 2, the log file doesn't output a valid solution. I suspect the issue could stem from incorrect input file formatting, problems with the graph structure, or improper application of reduction rules.

Background on the Graph Setup #

The graph was built using Python's NetworkX. I've verified that every edge is reachable from the root node, set weights for each arc and its reverse, and configured the problem type as "SAP". Most edges are bidirectional with matching weights in both directions.

Input STP File #

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

Expected vs. Actual Result #

I expected the solution to include at least 10 edges to connect all required terminal nodes. However, when setting stp/reduction=2, the output solution is:

SECTION Finalsolution
Vertices 2
V 5
V 49
Edges 1
E 5 49
End

Troubleshooting Suggestions #

• Verify Terminal Reachability (Direction Matters!): Even though you confirmed general reachability, double-check if each target terminal (44,45,46,47,48) is reachable from root 49 via directed arcs. For example, the arc A 27 44 297.37 10000000000 allows travel from 27 to 44, but reverse travel has a prohibitive 1e10 weight. Ensure there's a valid directed path from root 49 to 27 first.
• Test with Reductions Disabled: Run SCIP-Jack with stp/reduction=0 (no reductions) to see if a valid solution is generated. If yes, the issue is likely with aggressive reduction rules incorrectly pruning necessary nodes/edges. You can then tweak reduction parameters to be less strict, or investigate why the rules are misbehaving with your graph.
• Validate STP Format Compliance:
  • Confirm that SAP problem edges are correctly defined: Some STP implementations require separate directed arcs for each direction instead of using the A u v w1 w2 syntax for bidirectional edges.
  • Check extreme weights: The 1e10 reverse weights might be interpreted as "impassable" by reduction rules, effectively making those edges one-way. Ensure this aligns with your intended graph structure.
• Check NetworkX-to-STP Conversion: Make sure your conversion script correctly translates NetworkX edges to STP arcs, preserving direction and weight values. It's easy to accidentally flip arc directions or misassign weights during export.

内容的提问来源于stack exchange，提问作者b9s