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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.