1
$\begingroup$

Suppose we have a 6 vertices graph. We also have 6 gates. Each gate is attributed a path.

For example,

Gate 'A' will have to go to 'B'- 'C' - 'D' and 'E'

Gate 'B' will have to go to 'D'

Gate 'C' will have to go to 'A' and 'B'

Gate 'D' will have to go to 'E' - 'A' and 'B'

Gate 'E' will have to go to 'C' - 'E' and 'A'

Gate 'B' will have to go to 'D'

How can I find the optimal placement of the gates on the graph, such that it makes the least distance overall, computing all the paths to be made?

For 6 gates, we could search all possible placements by brute force. However, in my current project I have 42 gates to dispatch, thus it sounds too complicated to brute force.

The following is the function used to calculate the distance between the two gates (stocked in a Pandas DataFrame)

import math
def calculateDistance(df, gate_a, gate_b):
    coord_a = [(x, df.columns[y]) for x, y in zip(*np.where(df.values == gate_a))][0] # GET COORDINATE OF GATE_A
    coord_b = [(x, df.columns[y]) for x, y in zip(*np.where(df.values == gate_b))][0] # GET COORDINATE OF GATE_B
    y1, x1 = coord_a[0], coord_a[1]
    y2, x2 = coord_b[0], coord_b[1]
    dist = math.sqrt((((x2 - x1) * scale_x) **2)  + ( ((y2 - y1) * scale_y) **2 ))
    return dist
    
calculateDistance(df, "A", "C")
$\endgroup$
5
  • $\begingroup$ I've added the way I calculate the distance between two gates, finding the gate's coordinates within the dataframe. $\endgroup$
    – Achille G
    Jul 25 at 15:13
  • $\begingroup$ The least distance overall, computing all the paths to be made! Sorry if this is not clear $\endgroup$
    – Achille G
    Jul 25 at 15:21
  • $\begingroup$ No, in my current project I have 42 gates to dispatch, thus it sounds too complicated to brute force $\endgroup$
    – Achille G
    Jul 25 at 15:34
  • $\begingroup$ Travelling salesman problem is a very special case of your task. It is unlikely there is an algorithm in polynomial time of the number of gates. $\endgroup$
    – John L.
    Jul 25 at 15:57
  • 2
    $\begingroup$ Let me do my best attempt to rephrase the problem in CS terms: There's a metric space $X$, with $n$ points. Additionally, there is a collection of $n$ sequences of labels, where all labels are numbers in $\{1, \ldots, n\}$, and all sequences start with a different label. When the points are labeled in bijection to $\{1, \ldots, n\}$ then each sequence defines a path. The problem is to choose a bijective labeling of the nodes that minimizes the sum of the lengths of paths induced by the sequences? Is this a correct interpretation? If so your problem is clearly NP-hard as suggested by @JohnL. $\endgroup$ Jul 25 at 16:57

1 Answer 1

2
$\begingroup$

Based on the reformulation of your problem from Bernardo Subercaseaux, your problem is NP-hard (as John L explains), so you should not expect an algorithm that will be efficient in the worst case.

That said, 42 is a fairly small number, so there is some hope. I would suggest that you formulate this as an instance of integer linear programming (ILP). Add zero-or-one boolean variables $x_{v,i}$ for each vertex $v$ (i.e., point in the plane) and each gate $i$ (i.e., each index in $\{1,2,\dots,n\}$), where $x_{v,i}=1$ means that $v$ is associated with $i$. Add constraints to enforce that this is a bijective mapping, i.e., $\sum_v x_{v,i}=1$ for all $i$ and $\sum_i x_{v,i}=1$ for all $v$. Also, for each $v,w,i,j$ let $y_{v,i,w,j} = x_{v,i} \land x_{w,j}$, which can be enforced using linear inequalities as explained in Express boolean logic operations in zero-one integer linear programming (ILP). Finally, you now have an objective $\Phi$ defined as

$$\Phi = \sum_{i,j} \sum_v \sum_w d(v,w) y_{v,i,w,j}$$

where $d(v,w)$ is the distance between $v$ and $w$ (a constant), and you sum over all edges $(i,j)$ that appear in the input sequences, and you sum over all possible $v$ and $w$. This objective is a linear function, so you can use an ILP solver to find the solution that minimizes $\Phi$. You'll end up with an ILP instance with several million variables and tens of millions of inequalities, which might be small enough that an off-the-shelf ILP solver can solve it to find a decent solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.