Performance features

All features on this page preserve the optimum: enabling (or disabling) any of these flags returns the same optimal objective (or, for the heuristic-only mode, a certified bound on it). The heavy graph reductions are on by default; the dual-ascent features remain opt-in.

Dual-ascent accelerator

An optional Wong (1984) dual-ascent procedure can speed up the exact solve. It computes, cheaply, a lower bound, a feasible primal solution, and reduced costs; following Leitner et al. (2018) the reduced costs are used to fix variables to zero (eliminate arcs/edges that cannot appear in any optimal solution) before HiGHS/Gurobi runs. When the bound matches the heuristic, the instance is solved without building the ILP at all.

# Enable per problem (constructor) ...
solution = SteinerProblem(graph, terminal_groups, dual_ascent=True).get_solution()

# ... or per call (overrides the constructor flag)
solution = SteinerProblem(graph, terminal_groups).get_solution(dual_ascent=True)

It is off by default and returns the same optimum as the baseline. Supported for Steiner tree, forest (multi-root), and directed (DirectedSteinerProblem) problems; it is skipped automatically when a budget or max_degree modifier is set, and for the prize-collecting / node-weighted variants.

When enabled it additionally warm-starts the cut loop with the Steiner cuts found during dual ascent and runs a multi-start primal from several roots, so many instances are solved entirely by dual ascent with no ILP.

Bound-based graph reduction

# Delete edges proven non-optimal by the dual-ascent reduced costs, then cascade
# the degree reductions — shrinking the model before the solve.
solution = SteinerProblem(graph, terminal_groups, da_reduce=True).get_solution()

da_reduce is a reduction test: it removes edges and nodes that the dual-ascent reduced costs prove cannot appear in any optimal solution (bound-based edge and node elimination) and cascades the degree-1/degree-2 reductions to a fixpoint. It requires preprocess=True (the default), applies to undirected problems only, is skipped under a budget/max_degree modifier, and preserves the optimum (solutions still map back to the original graph). It composes with dual_ascent=True.

Heavy graph reductions

# ON by default: Special Distance + long-edge deletion and node replacement,
# interleaved with the degree reductions to a fixpoint.
solution = SteinerProblem(graph, terminal_groups).get_solution()

# Disable them all ...
SteinerProblem(graph, terminal_groups, heavy=False)

# ... or take fine-grained control (each flag defaults to the `heavy` value):
SteinerProblem(graph, terminal_groups, special_distance=True, long_edge=False,
               replace_nodes=False)

heavy (default True) enables three classic alternative-based reduction tests from the Steiner-tree literature, each of which removes only what is provably compatible with an optimal solution and then cascades the degree-1/degree-2 reductions:

  • Special Distance (bottleneck Steiner distance) test — deletes an edge e = {v, w} when the bottleneck distance between v and w through the terminal distance network is below c(e) (Rehfeldt & Koch, Math. Prog. B 197, 2023, Thm 1; surveyed in Ljubić, Networks 77, 2021, §4). The bound routes through the two nearest terminals of each endpoint, a strict strengthening of the classic nearest-terminal bound. Steiner tree only (automatically skipped for the multi-group forest, where terminal-hopping would be unsound).

  • Long-edge / alternative-path test — deletes an edge when a strictly cheaper detour exists in G \ e. Valid for both Steiner tree and forest.

  • Node replacement (pseudo-elimination) — eliminates a non-terminal of degree ≤ 4 that provably has degree ≤ 2 in at least one minimum Steiner tree (Rehfeldt & Koch 2023, Prop. 4: the criterion compares the largest terminal-MST weights against the cheapest incident edges), bridging each neighbour pair with the two-edge path cost. Replacement edges are pre-filtered by the Special Distance bound and merged into cheaper parallels, so the graph never grows. Steiner tree only.

The tests are implemented with the fast constructions used by state-of-the-art SPG solvers: a single two-label multi-source Dijkstra (terminal Voronoi diagram) plus Mehlhorn’s (1988) boundary MST — O(m + n log n) rather than one shortest-path tree per terminal — shared by the Special Distance and replacement tests, and one bounded Dijkstra per vertex rather than per edge for the long-edge test (Rehfeldt & Koch 2023, §2.3). The degree-1/degree-2 cascades run in place off a change-driven worklist.

heavy requires preprocess=True (the default), applies to undirected problems only, is skipped under a budget/max_degree/hop_limit modifier (those variants do not minimise plain edge cost), and preserves the optimum value — solutions still map back to the original graph, though among several equal-cost optima a different one may be returned than with heavy=False. It composes with da_reduce=True and dual_ascent=True; a good “throw everything at it” configuration is:

SteinerProblem(graph, terminals, da_reduce=True, dual_ascent=True)

Terminal contraction

Four inclusion tests run alongside the deletion tests (on by default, contract_terminals=False opts out; Steiner tree only):

  • Degree-1 terminal contraction — a terminal’s sole incident edge is in every feasible solution, so it is fixed and the terminal merged into its neighbour.

  • Adjacent-terminal contraction — an edge between two terminals that is a cheapest edge incident to one of them is in at least one optimal solution (the classic cut-exchange argument), so it is fixed and the terminals merged.

  • Nearest Vertex (NV) (Polzin & Vahdati Daneshmand 1998, Obs. 3.2) — a terminal’s cheapest incident edge {t, v'} is fixed when c(e') + d(v', tj) ≤ c(e'') for another terminal tj (second-cheapest incident cost c(e'')), certified from the two-label Voronoi diagram.

  • Short Links (SL) (ibid., Obs. 3.3) — the cheapest edge leaving a terminal’s Voronoi region is fixed when every other leaving edge costs at least its full link length d(t,u) + c(u,w) + d(w, base(w)); the merged endpoint is promoted to a terminal.

Fixing an edge moves its cost out of the reduced model (it is added back to every reported objective) and shrinks the terminal set, which in turn strengthens the Special-Distance and replacement tests — the cascade can solve an instance outright during preprocessing, in which case no solver runs at all. Solutions still map back to the original graph, and the optimum value is preserved exactly.

Bound-based deletions (BND)

Using the terminals’ Voronoi radii (cheapest way to leave each region) and a shortest-path-heuristic upper bound, any node with d1(v) + d2(v) + Σ smallest (s−2) radii > UB — and any edge with c(e) + d1(u) + d1(w) + Σ radii > UB — is provably not needed in any optimal solution and is deleted (Polzin & Vahdati Daneshmand 1998, Obs. 3.5/3.6). On by default with the heavy tests; opt out with bound_based=False.

Few-terminal dynamic program

For a plain (undirected, single-group, unconstrained) Steiner tree with few terminals, the exact Dreyfus–Wagner (1971) dynamic program — in the Erickson–Monma–Veinott (1987) formulation — solves the reduced instance outright, bypassing the ILP entirely. This is the reductions + DP recipe of the winning PACE 2018 solvers; it is O(3^k) in the terminal count k but only linearithmic in the graph size, so for small k it beats any branch-and-cut by a wide margin (4–30× on benchmarked instances).

It is auto-selected after preprocessing whenever the (reduced) terminal count is at most STEINERPY_DW_MAX_TERMINALS (default 10; 0 disables), returns the identical optimum with gap == 0.0, and transparently accelerates the transformed group-Steiner, terminal-leaf and rectilinear variants as well.

Cut-separation accelerators

The exact solve enforces connectivity lazily with directed Steiner cuts found by minimum-cut separation. Three classic accelerators are applied automatically (no flags needed):

  • LP-first separation (Koch & Martin 1998) — on the HiGHS path the cut loop first runs on the LP relaxation: each round is a cheap LP re-solve, and the accumulated root cuts strengthen every subsequent MIP solve (5–10× on benchmarked tree instances). Tune or disable with STEINERPY_LP_CUT_ROUNDS (default 50, 0 disables). The Gurobi path separates fractional points inside its branch-and-cut callback instead.

  • Creep flows and back cuts (Schmidt, Zey & Margot 2021, §4.1) — bias each minimum cut towards few arcs, and add the terminal-side cut alongside the root-side one.

  • Nested cuts (Koch & Martin 1998) — after a violated cut is found, its arcs are saturated and the max-flow re-run, yielding a second, structurally different violated cut per round. Extra max-flows are spent only on violated terminals. Tune or disable with the STEINERPY_NESTED_CUTS environment variable (default 1, 0 disables; higher values add more cuts per round but grow the model faster than they save re-solve rounds on the HiGHS path).

All of these change only how fast the cut loop converges, never the optimum.

Heuristic-only mode

An exact solver can’t match a polynomial-time heuristic such as networkx.steiner_tree in general. When you want that speed and can accept an approximate answer, pass exact=False:

# Return the dual-ascent primal directly — no ILP is built or solved.
solution = SteinerProblem(graph, terminal_groups).get_solution(exact=False)

print(solution.objective)  # heuristic tree weight (an upper bound on the optimum)
print(solution.gap)        # PROVEN optimality gap: 0.0 == provably optimal

Unlike a pure heuristic, the returned Solution.gap is a valid optimality certificate: gap == 0.0 means the heuristic tree is provably optimal, and a positive gap bounds how far it could be from the optimum — something networkx.steiner_tree (which gives no lower bound) cannot provide. It is supported for plain Steiner tree/forest and directed problems, and raises NotImplementedError for the budget/degree-constrained variants. The default is exact=True (solve to optimality).

Prize-collecting / MWCSP acceleration

PrizeCollectingProblem and MaxWeightConnectedSubgraph default to a penalty/Big-M flow ILP. For the classic forgo-prize PCSTP (and the MWCSP) you can opt into a much faster path that — following Rehfeldt & Koch (MWCSP 2019; PCSTP 2020) — transforms the problem to a rooted Steiner arborescence and reuses the dual-ascent + directed-cut machinery:

# Exact, accelerated (often proves optimality without any ILP):
sol = PrizeCollectingProblem(graph, [[root]], node_prizes, penalty_cost=0).get_solution(pc_transform=True)

# Heuristic-only: dual-ascent primal, no ILP, with a PROVEN optimality gap:
sol = PrizeCollectingProblem(graph, [[root]], node_prizes, penalty_cost=0).get_solution(exact=False)

# Prize-safe edge reduction (prize-constrained distance) before solving:
sol = PrizeCollectingProblem(graph, [[root]], node_prizes, penalty_cost=0, pc_reduce=True).get_solution(pc_transform=True)

# MWCSP uses the exact MWCSP -> PCSTP -> SAP mapping:
sol = MaxWeightConnectedSubgraph(graph, node_weights).get_solution(pc_transform=True)

All three flags are off by default (the penalty ILP is unchanged) and gated to the classic forgo-prize objective: a penalty_budget, multiple terminal groups, or a non-zero penalty_cost raises NotImplementedError (use the default penalty ILP for those). pc_reduce deletes only edges provably in no optimal solution and removes no nodes, so every prize is preserved.