Example of solving a Steiner Tree/Forest Problem using HighsPy¶
This example demonstrates how to use the HighsPy library to solve a Steiner Tree Problem on a simple graph. We will create a graph with nodes and edges, define the terminals we want to connect, and then use the SteinerProblem class to find the optimal solution.
import networkx as nx
from steinerpy import SteinerProblem
We make a simple example with four nodes and four edges. We want to connect A, B, and D. The optimal solution is AC, BC, and CD.
graph = nx.Graph()
edges = [("A", "C"), ("A", "D"), ("B", "C"), ("C", "D")]
weights = [1, 10, 1, 1]
for i, edge in enumerate(edges):
graph.add_edge(edge[0], edge[1])
graph.edges[edge][f"weight"] = weights[i]
We now create a SteinerProblem instance with the graph and the terminals we want to connect. We then call the get_solution method to solve the problem, specifying a time limit of 300 seconds.
solution = SteinerProblem(graph, [["A", "B", "D"]]).get_solution(time_limit=300)
INFO:root:Building the model.
INFO:root:Model built in 0.00 seconds.
INFO:root:Started with running the model...
INFO:root:Runtime: 0.01 seconds
Running HiGHS 1.12.0 (git hash: 755a8e0): Copyright (c) 2025 HiGHS under MIT licence terms
MIP has 46 rows; 37 cols; 124 nonzeros; 21 integer variables (21 binary)
Coefficient ranges:
Matrix [1e+00, 1e+00]
Cost [1e+00, 1e+01]
Bound [1e+00, 1e+00]
RHS [1e+00, 1e+00]
Presolving model
30 rows, 23 cols, 78 nonzeros 0s
20 rows, 16 cols, 54 nonzeros 0s
11 rows, 7 cols, 29 nonzeros 0s
9 rows, 6 cols, 22 nonzeros 0s
5 rows, 5 cols, 12 nonzeros 0s
4 rows, 4 cols, 10 nonzeros 0s
Presolve reductions: rows 4(-42); columns 4(-33); nonzeros 10(-114)
Objective function is integral with scale 1
Solving MIP model with:
4 rows
4 cols (4 binary, 0 integer, 0 implied int., 0 continuous, 0 domain fixed)
10 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
u 0 0 0 100.00% -inf 3 Large 0 0 0 0 0.0s
1 0 1 100.00% 3 3 0.00% 0 0 0 0 0.0s
Solving report
Status Optimal
Primal bound 3
Dual bound 3
Gap 0% (tolerance: 0.01%)
P-D integral 0
Solution status feasible
3 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.01
Max sub-MIP depth 0
Nodes 1
Repair LPs 0
LP iterations 0
We can now access the selected edges in the optimal solution, as well as the optimality gap, runtime, and objective value.
solution.selected_edges
[('A', 'C'), ('C', 'B'), ('C', 'D')]
print(f"Optimality gap: {solution.gap:.2f}")
print(f"Runtime: {solution.runtime:.2f} sec")
print(f"Objective: {solution.objective:.2f}")
Optimality gap: 0.00
Runtime: 0.01 sec
Objective: 3.00
In case you’re interested in Steiner Forest Problems, you can define multiple sets of terminals to connect. For example, we can connect A and B in one set and C and D in another set.
solution = SteinerProblem(graph, [["A", "B"], ["C", "D"]]).get_solution(time_limit=300)
INFO:root:Building the model.
INFO:root:Model built in 0.00 seconds.
INFO:root:Started with running the model...
INFO:root:Runtime: 0.00 seconds
Running HiGHS 1.12.0 (git hash: 755a8e0): Copyright (c) 2025 HiGHS under MIT licence terms
MIP has 86 rows; 63 cols; 224 nonzeros; 31 integer variables (31 binary)
Coefficient ranges:
Matrix [1e+00, 1e+00]
Cost [1e+00, 1e+01]
Bound [1e+00, 1e+00]
RHS [1e+00, 1e+00]
Presolving model
50 rows, 37 cols, 121 nonzeros 0s
29 rows, 21 cols, 76 nonzeros 0s
22 rows, 15 cols, 55 nonzeros 0s
18 rows, 11 cols, 43 nonzeros 0s
14 rows, 10 cols, 32 nonzeros 0s
9 rows, 6 cols, 19 nonzeros 0s
6 rows, 4 cols, 13 nonzeros 0s
4 rows, 3 cols, 9 nonzeros 0s
1 rows, 2 cols, 2 nonzeros 0s
0 rows, 1 cols, 0 nonzeros 0s
0 rows, 0 cols, 0 nonzeros 0s
Presolve reductions: rows 0(-86); columns 0(-63); nonzeros 0(-224) - Reduced to empty
Presolve: Optimal
Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 3 3 0.00% 0 0 0 0 0.0s
Solving report
Status Optimal
Primal bound 3
Dual bound 3
Gap 0% (tolerance: 0.01%)
P-D integral 0
Solution status feasible
3 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.00
Max sub-MIP depth 0
Nodes 0
Repair LPs 0
LP iterations 0
Node-Weighted Steiner Tree (NWST)¶
In the Node-Weighted Steiner Tree problem, nodes have costs rather than (or in addition to) edges. The goal is still to find a minimum-cost connected subgraph that spans a set of terminals, but now both node and edge costs contribute to the objective.
Internally, each node v is split into v_in and v_out connected by a directed edge whose cost equals the node weight. The resulting edge-weighted directed graph is then solved with the standard formulation.
Use NodeWeightedSteinerProblem(graph, terminal_groups, node_weights) to model this variant.
from steinerpy import NodeWeightedSteinerProblem
# Triangle graph: going via B is expensive (weight 10) so the optimal
# solution connects A and C directly.
G_nw = nx.Graph()
G_nw.add_edge('A', 'B')
G_nw.add_edge('B', 'C')
G_nw.add_edge('A', 'C')
node_weights = {'A': 1, 'B': 10, 'C': 1}
nw_solution = NodeWeightedSteinerProblem(G_nw, [['A', 'C']], node_weights).get_solution(time_limit=30)
print(f'Objective (node + edge costs): {nw_solution.objective:.2f}') # 2.0
print(f'Selected edges: {nw_solution.selected_edges}') # [(A, C)]
print(f'Selected nodes: {nw_solution.selected_nodes}') # [A, C]
Maximum-Weight Connected Subgraph (MWCS)¶
The Maximum-Weight Connected Subgraph problem asks for a connected subgraph whose total node weight is maximised. Nodes may have positive or negative weights; the solver naturally excludes negative-weight nodes unless they are necessary connectors.
Use MaxWeightConnectedSubgraph(graph, node_weights) — a convenience subclass of PrizeCollectingProblem that automatically sets up the prize-collecting formulation.
from steinerpy import MaxWeightConnectedSubgraph
G_mwcs = nx.Graph()
G_mwcs.add_edge('A', 'B', weight=0)
G_mwcs.add_edge('B', 'C', weight=0)
G_mwcs.add_edge('C', 'D', weight=0)
node_weights_mwcs = {'A': 2, 'B': 3, 'C': 1, 'D': -10} # D is strongly negative
mwcs_solution = MaxWeightConnectedSubgraph(G_mwcs, node_weights_mwcs).get_solution(time_limit=30)
print(f'Selected nodes: {mwcs_solution.selected_nodes}') # A, B, C (D excluded)
print(f'Total prize (= total node weight): {mwcs_solution.total_prize:.2f}') # 6.0
Degree-Constrained Steiner Tree¶
The Degree-Constrained Steiner Tree problem adds the restriction that no node in the solution may have more than max_degree incident edges. One linear constraint per node is added to the MIP:
Pass max_degree=D as a keyword argument directly to any problem class — no dedicated class is required.
The same modifier can be combined with budget or used with PrizeCollectingProblem, etc.
from steinerpy import SteinerProblem
G_deg = nx.Graph()
for u, v, w in [('A','B',1), ('B','C',1), ('C','D',1), ('A','C',1), ('B','D',1)]:
G_deg.add_edge(u, v, weight=w)
deg_solution = SteinerProblem(
G_deg, [['A', 'D']], max_degree=2
).get_solution(time_limit=30)
print(f'Objective: {deg_solution.objective:.2f}')
print(f'Selected edges: {deg_solution.selected_edges}')
# Verify degree constraint
for node in G_deg.nodes():
deg = sum(1 for e in deg_solution.selected_edges if node in e)
print(f' degree({node}) = {deg} (<= 2)')
Budget-Constrained Steiner Tree¶
The Budget-Constrained Steiner Tree problem flips the optimisation direction: given a maximum total edge-cost budget, maximise the number of connected terminals. A single budget constraint is added:
and the objective becomes minimising the number of unconnected terminals.
Pass budget=B as a keyword argument directly to any problem class — no dedicated class is required.
You can combine budget with max_degree or use it alongside PrizeCollectingProblem, etc.
G_bud = nx.Graph()
G_bud.add_edge('A', 'B', weight=1)
G_bud.add_edge('B', 'C', weight=1)
G_bud.add_edge('C', 'D', weight=1)
# With budget 2 we can afford at most 2 edges in this chain → connect 3 of 4 terminals
bud_solution = SteinerProblem(
G_bud, [['A', 'B', 'C', 'D']], budget=2.0
).get_solution(time_limit=30)
print(f'Connected: {bud_solution.connected_terminals} / {bud_solution.total_terminals}')
print(f'Selected edges: {bud_solution.selected_edges}')
# Combining both modifiers: budget + degree constraint
combo_solution = SteinerProblem(
G_bud, [['A', 'B', 'C', 'D']], max_degree=2, budget=2.0
).get_solution(time_limit=30)
print(f'\nWith max_degree=2 + budget=2.0:')
print(f'Connected: {combo_solution.connected_terminals} / {combo_solution.total_terminals}')
print(f'Selected edges: {combo_solution.selected_edges}')
Directed Steiner Tree (Steiner Arborescence)¶
In the Directed Steiner Tree (also known as the Steiner Arborescence Problem), the graph is directed (nx.DiGraph) and a designated root node must reach every terminal via directed paths. Only arcs in the direction they exist in the DiGraph are considered — no reverse arcs are added.
Use DirectedSteinerProblem(digraph, root, terminals).
from steinerpy import DirectedSteinerProblem
DG = nx.DiGraph()
DG.add_edge('A', 'B', weight=1)
DG.add_edge('B', 'C', weight=1)
DG.add_edge('A', 'C', weight=10) # Direct but expensive
dir_solution = DirectedSteinerProblem(DG, root='A', terminals=['B', 'C']).get_solution(time_limit=30)
print(f'Objective (A→B→C): {dir_solution.objective:.2f}') # 2.0
print(f'Selected arcs: {dir_solution.selected_edges}') # [(A,B), (B,C)]
# Each arc is one-directional; reverse arcs (e.g. C→A) are not present
for u, v in dir_solution.selected_edges:
print(f' Arc ({u}→{v}) exists in DiGraph: {DG.has_edge(u, v)}')
Choosing the Solver¶
By default, SteinerPy uses the HiGHS solver (open-source, always available). If you have access to Gurobi (with a valid license), you can switch to it via the solver parameter on get_solution().
When Gurobi is chosen, connectivity constraints are enforced via lazy-cut callbacks inside Gurobi’s branch-and-cut engine — the same cut-based formulation (DO-D) as the HiGHS backend, but exploiting Gurobi’s internal branch-and-bound tree. This can significantly reduce runtime on larger instances.
Requirements for Gurobi:
pip install gurobipyA valid Gurobi license (free academic licenses are available at https://www.gurobi.com/academia/academic-program-and-licenses/)
import importlib
# Check if gurobipy is available
gurobi_available = importlib.util.find_spec("gurobipy") is not None
if gurobi_available:
# Solve with Gurobi using lazy-cut callbacks
solution_gurobi = SteinerProblem(graph, [["A", "B", "D"]]).get_solution(
time_limit=300, solver="gurobi"
)
print(f"Gurobi objective: {solution_gurobi.objective:.2f}")
print(f"Gurobi selected edges: {solution_gurobi.selected_edges}")
else:
print("gurobipy is not installed. Install it with: pip install gurobipy")
print("Falling back to HiGHS (default solver)...")
solution_highs = SteinerProblem(graph, [["A", "B", "D"]]).get_solution(
time_limit=300, solver="highs"
)
print(f"HiGHS objective: {solution_highs.objective:.2f}")