Networks (experimental)

The two engines

How the Heuristic greedy tree and the MILP fixed-charge optimiser design a network — conceptual explanation and trade-offs.

Both engines take the same COMET cost surface as input and produce the same network.gpkg output. They differ in how they decide which pipes to build and where flows should merge.

Experimental feature. Networks mode is under active development. Some technical aspects are still being validated with domain researchers. If you find results that don’t make sense, please open a GitHub issue or email co2gis.support@gmail.com.

Heuristic (fast)

The heuristic grows a least-cost tree one source at a time, always routing toward the whole network built so far rather than toward a fixed sink. This lets later sources snap onto corridors already laid, so trunks form early.

Algorithm (simplified):

1. Seed the network with the sink cells.
2. Sort sources by descending flow (highest flow first — this becomes the first trunk spine).
3. For each source: run r.cost from the entire current network (multi-origin), then r.drain from the source to the nearest network cell. Add the drained path to the network.
4. Rebuild full source→sink chains, overlay them, and detect junctions where ≥2 paths merge.

Because every source drains onto a surface whose origins are the current network, the paths form a tree: once two paths reach a common cell they follow the same downstream cells, so junctions arise naturally without any explicit merge logic.

Properties:

• Connects every source — no selection.
• Trunks form implicitly from cell overlap.
• Fast: one r.cost per source.
• No extra dependencies.
• Result is a good greedy tree, not provably optimal.

MILP (optimal)

The MILP solves a fixed-charge network-design integer program: over a candidate graph of nodes and arcs, it decides which links to build, at which standard pipe diameter, and how CO₂ flows from sources through junctions to sinks — at minimum total cost, subject to a capture target.

How the candidate graph is built:

• Nodes: sources, sinks, and a regular grid of junction candidates (Steiner points). Smaller grid spacing → more candidates → closer to true optimum → slower.
• Arcs: each node’s k nearest neighbours by Euclidean distance (pruned to keep the graph tractable).
• Arc costs: for each arc, r.cost is run from one endpoint and sampled at the other to get the true COMET-weighted cost.

How trunks emerge: A junction node has no flow or capacity of its own — it is a pure pass-through. When two source spurs arrive at a junction, flow conservation forces the downstream arc to carry their combined flow. A larger pipe at that combined flow is cheaper per unit than two parallel smaller pipes. Trunks fall out of the economics without being explicitly programmed.

The optimiser also selects which sources to connect. Given a capture target (Mt/yr), it picks the cheapest subset of sources that meets it. This makes it useful when connecting every source is not necessary or not cost-effective.

Candidate-graph density presets:

Finer runs more r.cost passes (one per node) and a larger integer program. Start Coarse, then refine.

Properties:

• Selects an optimally chosen source subset meeting the capture target.
• Trunks form explicitly via flow conservation at junctions.
• Provably minimum-cost (within the candidate graph — not globally optimal over the full raster).
• Requires pulp + highspy (pip install pulp highspy into the QGIS Python environment).
• Slower than the heuristic; runtime driven by candidate-graph density.

The full mathematical formulation (sets, variables, objective, constraints) is in src/core/networks/milp.py.