Munchkin Workshop Research Project

This package implements solutions to a pairwise minimisation problem:

Given $2N$ particles in $M$ dimensions, return the optimal pairing such that the sum of intra-pair distance $d$ is minimised.

Usage

import pair_solver

solution, loss = pair_solver.mc_solution(particle_coordinates)

where particle_coordinates is a numpy array of $(2N, M)$ particle coordinate. The pairings corresponding to the approximate solution are stored in solution, and loss is the corresponding value of the sum of intra-pair distances.

In 1D, the solution is trivial - the $2N$ particles are sorted by coordinate value and neighbouring particles are paired together. This implementation is very fast and scalable. The code will automatically check if the coordinates are one-dimensional, and automatically return the 1D solution.

In MD, the solution is nontrivial - the current implementation returns an approximation numerical solution. First, a PCA projection is performed, transforming the particle coordinates into one dimension where the solution is trivial as mentioned above. This solution is used as the initial guess from which we perform Monte-Carlo optimisation by randomly changing the pairing of particles in the solution.

Additional arguments for the length of the Monte-Carlo opimisation as well as the parameters for the simulated annealing can be specified - please see the details in the docs.

Workflow Schematic

A simple illustration of the implementation is shown below:

graph TD;
  coords("(2N,M) particle coordinates")-->dist_mat(Distance matrix D); 
  coords -- PCA --> one_d("(2N, 1) One Dimensional Projection")
  one_d -- sort --> approx_soln(Initial Pairing)
  approx_soln --> MC(Monte-Carlo Optimizer)
  dist_mat --> MC
  MC -- "simulated annealing" --> improved_soln(Improved Solution)
  improved_soln --> improved_target(Improved Loss Value)