steinerpy 1.0.0

Package to solve Steiner Tree and Steiner Forest Problems with the HiGHS solver

SteinerPy

A Python package for solving Steiner Tree and Steiner Forest Problems — and several advanced variants — using the HiGHS solver and NetworkX graphs. Gurobi is also supported as an alternative solver via lazy-cut callbacks.

Installation

Install SteinerPy from PyPI:

pip install steinerpy

Or using uv:

uv add steinerpy

Requirements

• Python 3.8+
• NetworkX
• HiGHS Solver (via highspy)

To use Gurobi as the solver, you additionally need:

• gurobipy (install with pip install gurobipy)
• A valid Gurobi license

Quick Start

import networkx as nx
from steinerpy import SteinerProblem

# Create a graph
G = nx.Graph()
G.add_edge('A', 'B', weight=1)
G.add_edge('B', 'C', weight=2)
G.add_edge('C', 'D', weight=1)

# Define terminal groups
terminal_groups = [['A', 'D']]

# Solve with HiGHS (default)
problem = SteinerProblem(G, terminal_groups)
solution = problem.get_solution()

print(f"Optimal cost: {solution.objective}")
print(f"Selected edges: {solution.selected_edges}")

# Solve with Gurobi (requires gurobipy + license)
solution_gurobi = problem.get_solution(solver="gurobi")
print(f"Gurobi optimal cost: {solution_gurobi.objective}")

Supported Problem Variants

Every variant below can be solved as a Steiner Tree (a single group of terminals that must all be connected) or as a Steiner Forest (multiple independent groups, each connected within itself but not necessarily to other groups). Simply pass a list of terminal lists to terminal_groups — one list for a tree, multiple lists for a forest.

Variant	Class	Description
Steiner Tree / Forest	SteinerProblem	Classic minimum-cost subgraph that connects one or more groups of terminals.
Prize-Collecting Steiner Tree / Forest	PrizeCollectingProblem	Each terminal carries a prize; the solver balances the prize collected against the edge and penalty costs, so not all terminals need to be connected.
Node-Weighted Steiner Tree / Forest	NodeWeightedSteinerProblem	Nodes carry costs instead of (or in addition to) edges. Internally uses a node-splitting transformation to convert the problem to a standard edge-weighted formulation.
Maximum-Weight Connected Subgraph	MaxWeightConnectedSubgraph	Finds a connected subgraph maximising the total node weight. Nodes with negative weights are included only when they are needed as connectors. Convenience subclass of PrizeCollectingProblem.
Directed Steiner Tree (Arborescence)	DirectedSteinerProblem	The graph is directed (nx.DiGraph) and a designated root node must reach every terminal via directed paths.

Optional Constraint Modifiers

The two side-constraints below are optional keyword arguments that can be combined freely with any problem class above:

Modifier kwarg	Effect
max_degree=k	Every node in the solution has at most k incident edges.
budget=B	Total edge cost may not exceed B; the solver maximises the number of connected terminals and returns a BudgetSolution.

# Degree-constrained Steiner tree
solution = SteinerProblem(graph, terminal_groups, max_degree=2).get_solution()

# Budget-constrained Steiner tree
solution = SteinerProblem(graph, terminal_groups, budget=10.0).get_solution()

# Both constraints together (previously impossible with dedicated classes)
solution = SteinerProblem(graph, terminal_groups, max_degree=2, budget=10.0).get_solution()

# Degree-constrained prize-collecting problem
solution = PrizeCollectingProblem(graph, terminal_groups, node_prizes, max_degree=3).get_solution()

Note: DegreeConstrainedSteinerProblem and BudgetConstrainedSteinerProblem are still available for backward compatibility but are deprecated — pass the corresponding kwargs to the base class instead.

Solver Selection

Every problem class exposes a solver parameter on get_solution(). Two backends are supported:

solver value	Backend	Notes
"highs" (default)	HiGHS via highspy	Always available; cut-based formulation solved iteratively (re-solve loop).
"gurobi"	Gurobi via gurobipy	Optional; requires gurobipy and a valid Gurobi license. Connectivity cuts are injected as lazy constraints inside a branch-and-cut callback, which lets Gurobi exploit its full branch-and-bound tree.

# Use HiGHS (default — no extra installation required)
solution = SteinerProblem(graph, terminal_groups).get_solution()

# Use Gurobi (requires gurobipy + license)
solution = SteinerProblem(graph, terminal_groups).get_solution(solver="gurobi")

Both solvers implement the same cut-based (DO-D) formulation from Markhorst et al. (2025) and produce identical optimal solutions. Gurobi may be faster on larger instances because callbacks avoid repeated re-solves from scratch.

Usage Examples

See the example.ipynb notebook for detailed usage examples.

Dependencies

• networkx: For graph representation and manipulation
• highspy: For optimization solving (HiGHS backend, required)
• gurobipy: For optimization solving (Gurobi backend, optional — requires a Gurobi license)

If you use this package in your research, please cite:

@article{markhorst2025future,
  title={Future-proof ship pipe routing: Navigating the energy transition},
  author={Markhorst, Berend and Berkhout, Joost and Zocca, Alessandro and Pruyn, Jeroen and van der Mei, Rob},
  journal={Ocean Engineering},
  volume={319},
  pages={120113},
  year={2025},
  publisher={Elsevier}
}