0

I've 2 matrices both with Nx2 elements. Any value is a float with 8-10 decimals and they represent respectively 'x' and 'y' of a point.

For any element couple (x, y) (x is in the first column, while y is in the second one) in the first array, I'd need to find the closest point in the second one. At any loop, once found, I need to remove that value from the second array.

Finally, my main objective would be to have the optimal solution so that there's a one-to-one mapping between any element of the first array with only one element of the second array, so that the closest value clause is met.

I created a NxN matrix where I computed the distance from any point of first array to any point of the second array via

scipy.spatial.distance.cdist

Code:

def find_nearest(X_start, X_end):
    mat = scipy.spatial.distance.cdist(X_start, X_end, metric='euclidean')
    new_df = pd.DataFrame(mat)
    return new_df;

enter image description here

The next step is to couple a starting point with a ending point and there should NOT be any intersection, that is a mapping one-to-one.

I thought to do it via a Integer programming (using this). So if m[i][j] is an element of the matrix NxN, I found those constraints

enter image description here

The problem is that I don't know how to write the objective function and so I'm note sure if I need to add any other constraint related to it.

Do you think this is a good path to follow? Last question seems to be not appreciated since I did not expose what I already did and thus they told me to move it (link) to here.

So here it is.

JackLametta
  • 169
  • What happens if the closest point in the second matrix to row 1 in the first matrix is also the close point to row 2 in the first matrix? Who wins? Keep in mind that, in a mathematical program, decisions are made simultaneously, not sequentially (as in a loop). So "always use the nearest point" and "match each point once" may be incompatible. – prubin Jun 09 '19 at 17:54
  • 1
    You might also want to consider posting future questions of this type at https://or.stackexchange.com/questions. (I'm not suggesting that you cross-post this one.) – prubin Jun 09 '19 at 17:56
  • @prubin In my mind I have to find the best solution, so if a point in the second array is already taken, I won't re-use it. – JackLametta Jun 09 '19 at 18:13
  • I'm afraid that doesn't answer my question. "Already taken" implies a sequence to the decisions, but in a MIP model the decisions are made simultaneously. Requiring that no point be used twice is fine, but then you either need to provide a criterion for adjudicating attempts to reuse a point (this guy gets preference over this one because ...) or you need to stipulate that conflicts of that sort are resolved arbitrarily (meaning you accept you will not always get the nearest point). – prubin Jun 10 '19 at 19:16

0 Answers0