Return to Question

I have a very challenging problem I am trying to solve.

I have a connected network consisting of lines (edges) and points (nodes). I must connect a subset of these nodes together along the shortest path.

I have a connected network consisting of lines (edges) and points (nodes). I must connect a subset of these nodes together along the shortest path.

Is this right? If so, how might I implement this?

If this is right, then how might I implement it?

PROBLEM: Now the hard part. I am tasked with optimizing the network and have the freedom to cut end points from the network if it yields a more optimal value. The value I am seeking to minimize is the:

Z = sum(edge lengths in network) / number of end points connected

My first thought was to try to accomplish this heuristically - create the network that connects all end points to each other and then compute Z. Then remove an end point from the network and reconnect the remaining end points to each other and recompute Z. If Z has improved (lower value than before) formally remove that end point node from the graph. Keep iterating through all the end points until complete.

The issue is:

1. It is very time consuming to do the above.

2. It also does not guarantee an optimal solution. It would give me a different result each time depending on the starting end point.

I have considered a MILP solution using gulp in Python, but it is beyond my understanding. I think I might be stuck with a heuristic approach.

I have considered using a Steiner Tree, Minimum Spanning Tree, Traveling Salesman etc. to reconnect the end point nodes to each other along the network, but before I attempt to implement a solution, I was wondering if anyone has faced a similar problem?

Is there a better way for me to create a network with the lowest Z while maximizing the number of end points connected?

Is there a direct solution that can be found via networkx and Python?

PROBLEM: Now the hard part. I am tasked with optimizing the network and have the freedom to cut end points from the network if it yields a more optimal value. I believe the value I am trying to minimize is:

Z = sum edge lengths along path / number of connected addresses in path

As @FelixIP pointed out, there is an optimal solution and it would be a single address node not connected to anything:

Z = 0/1

I want to avoid that situation without providing hard coded constraints like minimum number of addresses to connect = 10. 

If I added an attribute (N) to every node, so that every node that is an endpoint of the green lines, but is not a red address point gets a value of 1 and all other nodes get a value of 0, perhaps I can ensure more than one address is connected by modifying my function to maximize:

Z = sum N for every node in path connecting addresses / sum length edges in path connecting addresses 

If I maximize that value, I am instructing the optimization algo to find the subnetwork connecting addresses so that the number of addresses connected to the network is as many as possible, while the total length of the subnetwork is as small as possible.

Is this right? If so, how might I implement this?