Optimise vertical position of nodes for shortest sum of paths

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

[Bjorn Gustavsson]

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?

[Michael Schumbach]

There are no such constraints. The only constraints are the x coordinate of nodes, the paths stating the nodes through which the paths have to go (in the given order), and that y coordinate has to be an integer greater than or equal to one. Also, the nodes cannot overlap.

Answer 1

[Bjorn Gustavsson]

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

[Michael Schumbach]

Thank you very much for your answer.

The above data is sample data, in reality I will be working with a matrix of about 400 paths with about 40 nodes assigned for each path and about 150 nodes in total. Do you have any suggestions regarding how could I implement the efficient integer-programming optimization algorithm?

[Bjorn Gustavsson]

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

[Michael Schumbach]

Thank you very much, I will have a look there.

Answer 2

[Steven Lord]

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.

[Michael Schumbach]

I will try following your suggestions. Thank you for your help.