7

I am trying to solve a large optimization problem where I have a set of nodes on a road network that need to be connected using fibre using the shortest possible amount of fibre.

The problem is a classical Steiner tree problem. Grass has a function called v.net.steiner but my road network consists of 20,000 edges connecting intersections and the number of Steiner nodes (points to be connected by fibre) is about 1500. I tried this on a 32-bit Linux OS with 4 GB of memory and I got an out of memory error.

Any suggestions on how to solve this with a desktop PC - or do I need to send the problem to a super-computer

I've attached an image of the problem - don't worry I will trim the dangle-roads but that only shaves off about 1000 road segments

Steiner Tree problem

4

2 Answers 2

1

Here I made an R package that could handle this problem. This tool uses that v.net.steiner algorithm, but uses it iteratively in order to get just the lines of the network that are relevant. Alfter iterate over n samples of your terminals, it calculates a new optimal Steiner Tree for the whole network.

So in resume, you will save ram because: - You don't need to open the whole QGIS interface. - Iterations of Steiner Tree are saved in the HDD (in a working grassdata folder). - The global Steiner Tree is calculated just with useful lines of the network.

Here is the R package: https://github.com/cesarkero/IterativeSteinerTree

Here is a simple code to use it (just change l and p for your lines and points layer):

Here you have an example of how to use it.

update.packages()
library(devtools)
install_github("cesarkero/IterativeSteinerTree")

library(IterativeSteinerTree)

# basic setGRASS (based on iniGRASS params but simplified)
setGRASS(gisBase = "/usr/lib/grass78", epsg= 25829)

# load sldf (l) and spdf (p)
data("l"); data("p")

# calculate Steiner Tree
IST <- IterativeSteinerTree(l, p[1:100,], th=1000, iterations = 25,
                            samples = 10, clean = TRUE, rpushbullet=FALSE)

enter image description here

The only problem is that this package just work in linux.

0

You can get an optimal solution to this problem by using the Steiner tree solver SCIP-Jack, see https://www.scipopt.org/doc/html/STP_MAIN.php, which is part of the SCIP Optimization Suite, see https://www.scipopt.org/.

You just need to write the problem in the .gr format (see https://pacechallenge.org/2018/steiner-tree/ Appendix A), to be able to solve it with SCIP-Jack.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.