6
$\begingroup$

I was doing the wiring of the sensors on my pinball machine and that lead me to an interesting optimization problem. There are 35 on/off sensors on the playfield of the machine. Behind the playfield, all those sensors need to be connected to a multi-pin connector, which in turn is connected to a microcontroller. I want to minimize the amount (total length) of wiring.

The sensors are connected to the connector using matrix wiring. This means that there are row-wires and column-wires. Every sensor is connected to one row-wire and one column-wire. Multiple sensors can use the same row-wire or the same column-wire, but each sensor needs a unique row-wire/column-wire pair.

We have a set of sensors $S = \{S_1, S_2, \dots,S_N\}$ and a connector $C$, which all lie in a metric space with distance function $d$. We could also say that $S \cup \{C\}$ is the set of vertices of a positively weighted complete graph. (2D Euclidean space may be assumed if that makes it easier)

We need to find two partitions of $S$: a row partition $S_r$ and a column partition $S_c$, under the condition $$\forall\ x \in S_r,\ y \in S_c:\ |x \cap y| \le 1.$$ The goal is to find partitions that minimize the total wiring length $$ T=\sum_{x \in S_r} W(x \cup \{C\}) + \sum_{y \in S_c} W(y \cup \{C\}). $$ Here $W(z)$ is a function that gives the total weight of the minimum spanning tree that connects all elements of $z$.

What is a fast algorithm to find optimal or reasonable $S_r$ and $S_c$ to minimize $T$?

Note: It is possible to use even less wiring if we allow a wire to split in different directions at a point that is not a sensor or connector, but to keep it simple let's not use that possibility.

Example

In the image, the black circles are the sensors, the red circle is the connector, the blue lines are the row wires and the green lines are the column wires.

Here we have $S_r = \{\{S_1,S_2,S_4\},\{S_3,S_5,S_6\}\}$ and $S_c = \{\{S_1,S_3\},\{S_2\},\{S_4,S_5\},\{S_6\}\}$. The wiring here is arbitrarily chosen by me, I don't know if it's optimal.

Example sensors

Idea

We don't have to consider combinations that have a minimum spanning tree with $C$ as an internal vertex.

For example, in the example above we don't have to consider any partitions that contain $\{S_2, S_6\}$, because $C$ is in the middle of $S_2$ and $S_6$, and we might just as well take $\{S_2\}$ and $\{S_6\}$ separately. However, it is still necessary to look at supersets of $\{S_2, S_6\}$.

Data

Here the $(x,y,z)$ locations of the controller (first in the list) and the 35 sensors:

[[46,21,2],[20,38,0],[20,32,0],[20,27,0],[20,22,0],[20,16,0],[20,40,4],[21,34,3],[21,22,3],[23,12,4],[27,48,1],[33,28,3],[33,11,4],[57,48,4],[48,46,4],[40,42,4],[41,15,0],[46,28,4],[42,33.5],[44.7,34.5,15],[47.4,35.5,15],[50.1,36.5,15],[52.9,37.5,15],[55.6,38.5,15],[58.3,39.5,15],[61,40.5,15],[59,11,4],[76,17,4],[78,10,0],[78,6,0],[105,24,0],[97,18,3],[97,37,3],[76,39,4],[79,43,0],[79,47,0]]

There are some obstacles below the playfield, so Euclidean distance is not entirely accurate, but for now that's good enough.

$\endgroup$
4
  • 1
    $\begingroup$ This is a tough problem. If you assume that every wire connects at most five sensors, you can precompute $W$ for all 324632 (= 35 choose 5) combinations, and solve the problem with mixed integer optimization. However, I do not see why 5 would be a good upper bound. $\endgroup$
    – LinAlg
    Commented Apr 24, 2020 at 16:40
  • $\begingroup$ @LinAlg That's an idea. But indeed, no reason to assume that this could be optimal. I added an idea to limit the search space to the question. $\endgroup$
    – Paul
    Commented Apr 27, 2020 at 13:48
  • $\begingroup$ Isn't this a modified version of the Traveling Salesman? I see no reason for this to be a simple problem. $\endgroup$
    – ViHdzP
    Commented Apr 27, 2020 at 14:32
  • $\begingroup$ I have an approach in mind. Do you have sample data I can try before posting my answer? $\endgroup$
    – RobPratt
    Commented Apr 27, 2020 at 20:32

1 Answer 1

3
+200
$\begingroup$

You can solve the problem via mixed integer linear programming. The idea is to design, for each of the two partitions, a minimum-cost network that enables sending one unit of flow from the connector (node $0$) to each node in $S=\{1,\dots,N\}$. Let $A$ be the directed arc set, with distances $d_{i,j}$, and let $P=\{1,2\}$ be the set of partitions. For $(i,j)\in A$ and $p\in P$, define nonnegative flow variable $x_{i,j,p}$ and binary variable $y_{i,j,p}$ to indicate whether $x_{i,j,p}>0$. For $\{i,j\} \subset S$ and $p\in P$, let binary variable $t_{i,j,p}$ indicate whether nodes $i$ and $j$ appear together in the same part of partition $p$. The problem is to minimize $\sum_{i,j,p} d_{i,j}\ y_{i,j,p}$ subject to linear constraints: \begin{align} \sum_{(j,i) \in A} x_{j,i,p} - \sum_{(i,j) \in A} x_{i,j,p} &= 1 &&\text{for $i \in S$ and $p \in P$} \tag 1\\ x_{i,j,p} &\le N\ y_{i,j,p} &&\text{for $(i,j) \in A$ and $p \in P$} \tag2\\ y_{i,j,p} + y_{j,i,p} &\le t_{i,j,p} && \text{for $0<i<j$ and $p \in P$} \tag3\\ t_{i,j,p} + t_{i,k,p} - 1 &\le t_{j,k,p} &&\text{for $0<i<j<k$ and $p\in P$} \tag4\\ t_{i,j,p} + t_{j,k,p} - 1 &\le t_{i,k,p} &&\text{for $0<i<j<k$ and $p\in P$} \tag5\\ t_{i,k,p} + t_{j,k,p} - 1 &\le t_{i,j,p} &&\text{for $0<i<j<k$ and $p\in P$} \tag6\\ \sum_{p\in P} t_{i,j,p} &\le 1 &&\text{for $0<i<j$} \tag7 \end{align} Constraint $(1)$ sends a net of one unit of flow to each node in $S$. Constraint $(2)$ enforces $x_{i,j,p} > 0 \implies y_{i,j,p}=1$. Constraint $(3)$ enforces $(y_{i,j,p} = 1 \lor y_{j,i,p} = 1) \implies t_{i,j,p}=1$. Constraints $(4)$, $(5)$, and $(6)$ enforce transitivity of togetherness. Constraint $(7)$ prevents each pair of nodes in $S$ from appearing together more than once.

This formulation yields the expected results for your $N=6$ instance. Here's the best solution I found so far for your $N=35$ instance: \begin{equation} \{1,2,4,8\}, \{3,6,7,11\}, \{5,9,12\}, \{10,15,17,18,19\}, \{13,22,23,33,34\}, \{14,20,21\}, \{24,31,32\}, \{25,26,30\}, \{27,28,29\}\\ \{1,6,10\}, \{2,11,17\}, \{3,4,5\}, \{7,8,9\}, \{12,16\}, \{13,14,15\}, \{18,21,23,24\}, \{19,20,22\}, \{25,28\}, \{26,27,32,33\}, \{29,30,31,34\} \end{equation} The objective value is $1027.5151123$.

Update: I now have a solution with objective value $972.68643098$. Also note that the minimum spanning tree cost is $309.47533082$, yielding a lower bound of twice that for the original problem.

$\endgroup$
5
  • $\begingroup$ I used the OPTMODEL procedure in SAS. $\endgroup$
    – RobPratt
    Commented Apr 28, 2020 at 16:46
  • $\begingroup$ Neat model. I tried creating a model with minimum spanning trees, but that obviously failed. $\endgroup$
    – LinAlg
    Commented Apr 30, 2020 at 12:56
  • $\begingroup$ Well, thanks for the answer! Such an approach didn't came to mind for me at all, so this really broadened my view. I'll test it myself later. $\endgroup$
    – Paul
    Commented Apr 30, 2020 at 17:52
  • $\begingroup$ So, you just leave it running for days? Does the software tell when it is optimal? $\endgroup$
    – Paul
    Commented May 1, 2020 at 11:47
  • 1
    $\begingroup$ Yes, you could just let it run for days, and the solver provides both lower and upper bounds all along the way. So either you let it run until these bounds agree or you stop early and get a measure of the "optimality gap" of the best solution that was found. But I am exploring different solver options and various modifications of this formulation. For example, you can relax $t$ to be nonnegative instead of binary because it will automatically take 0-1 values whenever $y$ does. Also, you can impose a cardinality constraint $\sum_{(i,j)\in A} y_{i,j,p} = N$ for each $p$. $\endgroup$
    – RobPratt
    Commented May 1, 2020 at 14:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .