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

Question

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

Personal background: got a master's in math, tutored/taught lower level math classes for several years, and took an operation research class before. (I knew how confusing this question is and I still feel the same thing now!)

Big picture: 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. Precheck of the space-usage can save some time. Pins and nodes are the same things. They are used interchangeably. [In a mathematical setting: connect the source (node A in block 1) to the destination (node A in block2) use the area available inside these dashed rectangles ("channels")(created in between these solid rectangles("blocks")) as straight lines].

Say I have some rectangle area left for channel routing after the placement, channel1, channel2, etc [I bet this may confuse people!!! You can forget how these channels are created and just focus on given avaiable channels which line goes to which channel] and I have 6 lines that may use channel 1 as an avenue for routing. They may cross the channel like that

For line 1 it crosses 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 the other line satisfies the jumping rule (which is more space requirements, and we relax that issue here). If this information bothers you forget about it and keep reading) [i.e., $line1.x = 0; line1.y = constant1$, but here I would keep $line1.x$ and $line1.y$ instead of switching to a number for easy generalization.]; For line 2 it crosses 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). In general, each line has line.x and line.y, i.e., $\begin{cases} \textrm{line i}.x = \textrm{constant} \textrm { or } 0\\\textrm{line i}.y = \textrm{constant} \textrm { or } 0 \end{cases}$, where $i$ is the line number.

Now you do get some idea, right?

So I set up 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.

The pic below shows the best case we want to see. There are 3 nodes in red indicating they are the same pin and connect 2 of them will make these two blocks connected. Rule of thumb, if there is a shorter path to connect 2 nodes use the shorter one. In our example, these two nodes are on the same level (the best situation ever) and a straight line is the best we can expect. Mathematically, line1 used some y-direction space and it finished its job. Y-Total space - line1.y and if no lines needs to use this channel in Y-direction that will conflict with line1 later. Then line 1 is meant to be stayed in this channel for the best routing result, i.e., $d_1 = 1$.

However, life is never easy for those who dream. For a case like the following pic we have to go around and take turns and uses more channels (not the channel before since there is something stuck in between)

2. Why we have a setup like that? 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 the time.)

We have 3 different ways to connect these 2 blocks with red nodes.

option1(red route): in channel 5 & 6 $\begin{cases} d_{1,5} = 1\\d_{1,6} = 1\end{cases}$

option2(blue route): in channel 1,2,3,4 & 5 $\begin{cases}d_{1,1} = 1\\d_{1,2} =1 \\d_{1,3} = 1\\ d_{1,4} =1 \\d_{1,5} =1\end{cases}$

option3(green route): in channel 5,7,8,9 & 10 $\begin{cases}d_{1,7} = 1\\d_{1,8} =1 \\d_{1,9} = 1\\ d_{1,10} =1 \\d_{1,5} =1\end{cases}$,

where $d_{i,j} = \begin{cases}1\\0 \end{cases}, i $ represents line number and $j $ represents channel number.

For my setup for each channel, line 1 will appear in all channels combined with other lines (if there is any).

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;
3. Channel is preset.

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. But I don't know how to solve for these $d_j$, where $j \in[1,17]$. These are binary variable either $1$ or $0$. 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 binary 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. Thanks for reading and I would like to discuss with whoever has any suggestions/comments.