Optimise vertical position of nodes for shortest sum of paths
1 view (last 30 days)
Show older comments
Hi, I am doing a project which aims to optimise the layout of nodes.
I have a matrix of many paths. Each row of the matrix is a separate path. Each path specifies through which nodes a path has to go from start to finish.
MATRIX OF PATHS = [a b c d e; a b d e g; a c b e g; a b c f; a b c d; a b c d e; a b d e; a b c f g]
Each of these nodes has an assigned x coordinate, however, the y coordinate has to be chosen in the most optimal way. The y coordinate has to be an integer that is equal to or greater than 1, so: (1,2,3,4...). The most optimal way is such that minimises the total length of paths.
LIST OF NODES: a: x=1 b: x=2 c: x=3 d: x=3 e: x=4 f: x=4 g: x=5
2 Comments
Bjorn Gustavsson
on 28 Oct 2022
What other constraints do you have? Fixed different start and end-points of the different paths? Some additional restrictions, like some maximum paths crossing one node? More?
Answers (2)
Bjorn Gustavsson
on 28 Oct 2022
If this is a one-off calculation just brute-force search shouldn't be too bad, the y-position of the nodes should be within a small range of integer values spanning no more than 7, you have seven y-values to search for. This makes the maximum combinations to look through 7^7, check that they fullfill your condition of notoverlapping and then calculate the total distances and keep those shorter than or equal to the currently shortest. No need to think or read up on an efficient integer-programming optimization algorithm that will take far longer time. Something like this to get you started:
shortest_total_path = inf;
for a = 1:7
for b = 1:7
for c = 1:7
for d = 1:7
for e = 1:7
for f = 1:7
for g = 1:7
Paths = {[[a;1], [b;2], [c;3], [d;3], [e;4]],...
[[a;1], [b;2], [d;3], [e;4], [g;5]],...
[[a;1], [c;3], [b;2], [e;4], [g;5]],...
[[a;1], [b;2], [c;3], [f;4]],...
[[a;1], [b;2], [c;3], [d;3]],...
[[a;1], [b;2], [c;3], [d;3], [e;4]],...
[[a;1], [b;2], [d;3], [e;4]],...
[[a;1], [b;2], [c;3], [f;4], [g;5]]};
% Calculate sum of the lengths of the paths
% save the total length in an array of with all lengths
% compare to currently shortest
% save this path if it is shorter
end
end
end
end
end
end
end
If on the other hand this is a problem where you will have to solve this type of tasks many times over you'll have to read up on efficient algorithms.
HTH
3 Comments
Bjorn Gustavsson
on 28 Oct 2022
Not really, there are some built-in functions for discrete optimization in the optimization toolbox. Perhaps you can find something there: linear-programming-and-mixed-integer-linear-programming, or here: nonlinear-problem-integer-nonlinear-constraints. There might be something on the file exchange: integer optimization.
HTH
Steven Lord
on 28 Oct 2022
If you have a graph or diagraph object representing your nodes and their connections, perhaps plotting the graph or digraph and using the layout function with the 'layered' layout option to determine on which level each node should be placed would help give you a starting point. You could then set the XData property of the object returned by the plot call to your known data and see how the plot looks.
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!