optimization – space usage in X and/or Y direction related to channel routing problem

I was asked about this during a job interview and here is how I summarize it into a math/operation research problem.

Analog routing is hard due to sensitive layout-dependent effects and varied performance metrics. So the algorithm applied to digital routing is not good enough to cover that. A pre-check of the space-usage can save some time. Pins and nodes are the same thing. They are used inter-changeably.

Say I have some rectangle area left for channel routing after the placement, channel1, channel2, etc and I have 6 lines that may use channel 1 as an avenue for routing. They may cross the channel like that channel routing.

For line 1 it cross channel1 in the X-direction, therefore it uses some y-space of channel1 and not x-space of channel1 (since we might jump over line 1, if other line satisfies the jumping rule (which is more space requirements and we relax that issue here)); For line 2 it cross channel1 in the Y-direction, therefore it uses some x-space of channel 1; For line 3, it makes a turn, thus both x and y-space are used; Line 4 it moves in a z-shape, thus both x and y – space are used (doubled in x-space). You get the idea.

So I setup a 10-channel situation to simulate a small analog routing scenarios.

Background info:

  1. if we have 3 pins named the same, node A, in order to connect all three we need at least 2 straight lines to connect them all (which is the best we want to see), but the real situation makes it hard to be true. We may need to use more lines or even longer lines to make the connection.
  2. Why we have a setup like that? sample we may have different locations for the same pins (for this example red node, and I showed 3 different ways to connect them and they use different channels for the majority of of the time.)

What do we know:

  1. each channel’s X-space and Y-space;
  2. each lines x and/or y-direction usage, i.e., line1.x = 0, line1.y = 8, etc.

What don’t we know: should I put line 1 in channel1; should I put line 2 in channel1; …

What do we want: is it possible to connect all the nodes we want for the layout like that? If not remove which line can make it work? Or which channel’s space needs to be enlarged in which direction so that this specific layout is working? The latter 2 questions is more advanced than I can think of now. So the questions is what kind of combination of these lines so that they can use as much space as possible and at the same time connect as many nodes as possible. (say we can put line 1,3, 5 in channel 1, line2,6,8 in channel2 and so on and no space violation and we connected say 10 nodes out of 13)

Here is my setup. I am not sure I am doing this right or not.

Setup and the next 9 channels are set up like that. But I don’t know how to solve for these $d_j$, where $j in(1,17)$. I want to find a systematic way to solve this (if this is the correct way to set it up) since in real world it may have hundreds/thousands of channels and we will be dealing with tons of variables. First glance gives me the feeling of constrained optimization/Big M method? I don’t know and feel like missing something but really have no clue what is the next step.