I have a set of n edges, e-star, which is the set of valid possible extra edges to an existing graph, G(v,e).
I want to minimise the median route path length across the network from a central point, c, to a set of destination points, b, by adding in the lowest number of best edges from e-star. As these edges have combinatorial effect on the route path lengths, it is not as simple as calculating the benefit of each edge, sorting, and picking the top 10 edges, for example. A combination of the lowest benefit edges might be better than the best edge by itself.
The pareto curve for this problem is the total length of edges added (to be minimised) and reduction in median route length compared to the base graph, G (to be maximised).
My first idea was to link edge selection to a binary vector of length n, feed this through a non-linear optimisation model, and use the vector to "switch on" (1) or "switch off" (0) edges. Eventually, this would tend toward a low cost, high score permutation of the input edges, e-star. However, this doesn't seem to work that well.
Any ideas on what this optimisation problem is comparable to? I have been looking into the Knapsack problem, as this is subset selection, but my research into the topic seems to indicate that the scores of items in Knapsack selection are not (typically) informed by other items chosen in tandem.