Bi-objective vertex-edge weighted steiner tree problem

Hello all,
What do you think bi-objective vertex-edge weighted Steiner tree problem, where there is a graph and weight on the vertices and edges, the objective is to find a tree with minimal weight on edge(sum of weight on edges) and minimal weight on vertices( sum of weight on vertices)?
These two objectives are two conflicting objectives?

Hi Benghelima,

I think you could find a tree, which minimizes the total cost of (vertices + edges) , but this will probably be not the same as the tree which minimizes either one of them.
Do you meant this by “conflicting objectives?”

hello dr,
By conflicting objectives? I mean that:
The minimization of the total weight of vertices increases the total weight of edges. and the minimization of the total weight of edges, increase the total weight of vertice.
So, what do you think about minimizing the total weight(vertices+edges) is better than finding all trees that have a compromise between both objectives( total weight of vertices, and total weight of vertices edges)?
Thank you

I am no expert on graphs but my intuition is that the optimization of the sum of each vertex and edge for a path is by definition a compromise between both objectives. So I think the two possibilities you mentioned above are the same thing. If they are not please explain why and maybe do a quick mock-up in grasshopper so the problem is not so abstract.

why the two possibilities you mentioned above are the same thing?
Find a tree that has minimal weight on edges is not the same where finding a tree with minimal weight on the vertices, are you agree on that?
For example: find a tree with total weight on vertice = 100 and the total weight on edge = 50, is not the same with a tree where the total weight on vertice = 70 and the total weight on edge = 80,

yes. I was referring to this:

I would try to do this so we can discus it in a more concrete setting:

what you mean by that?

Make a grasshopper definition showcasing the exact problem you are concerned with and share it here. Maybe have a look here: Help Us Help You


going from A to B is cheaper via the pink tree for edges but not for vertices.