Minimum Spanning Tree Problem - Constrained by total edge sum

Specific Domains Optimization (Mathematical)
1

Assume that I have an undirected graph. Several of the vertices in the graph serve as waste disposal sites, while the other vertices produce the waste. Producing vertices have a weight (corresponding to the amount of waste generated). The task is now to find clusters, in which edges connect disposal and production vertices such that a maximum of waste generated in the cluster is disposed of, while the sum of the connecting edges does not surpass an upper limit.

I am pretty new to the topic but my first idea was to loop through all disposal vertices and run a minimum spanning tree (MST) problem on each of them. If possible I would set a constraint in the MST to account for the upper limit of the summed length of edges. Furthermore, a second contraint regarding the minimum number of population served would be desirable.

I assume that by looping through all disposal vertices, some production vertices are included in several different clusters. To deal with that I thought of evaluating each cluster by some metric, e.g., dividing the total waste disposed by the summed edge length. So after having evaluated all clusters I would realize the best one (as measured by the metric), and take out the corresponding vertices from the graph. Then I would restart the loop again. This procedure would be continued until no clusters can be found anymore.

So my questions would be:

  1. Does this overall approach make sense? (Or are there aspects I miss out)
  2. Can I set constraints in a MST problem regarding the total edge length and the minimum vertices weight included?
2

Sounds like a flow problem.

Perhaps look-up:

And also, a minimal working example always helps the discussion get focused.

3

You should specify first some relevant conditions of your problem using standart notation / terms. Than it’s easier to reference to known problems / approaches.

From your description I assume that 1. all production vertices will be included in the solution (should be, but can be kicked out in the end). 2. there is only one commodity / one type of waste. 3. there are no capacity limits, each edge can transport infinite waste, each disposal site takes infinite waste.
Then I would try the following (using a dedicated algorithm instead of a more general optimization problem):

  1. add a “super disposal site” connected to all disposal sites (super source / sink).
  2. run (single source) shortest path from the super disposal site to all vertices. Each paths will contain an actual disposal site, you get a tree in the end. (not 100% sure but this should be minimum diameter trees then)
  3. if a path to a production side is too long, you can mark it as unservicable / infeasible.

Adding the population servicing constraint makes it much much harder. Sounds more like price collecting Steiner tree. MST is the “very nice and easy” version of that, where all vertices will be in the solution.

Maybe you could use the first idea’s path lengths as weights in Knapsack problem and select vertices this way, kind of as second stage.