Dispersion

This page cannot be shown here. You can still read it on the original site — the toolbar below keeps your place in the directory.

Find 10 points out of 50 with maximum distance from each other. 1 This problem can modelled as a max-min model where we maximize the smallest distance of 10 points. Model $$ \max \Delta\\ s.t.\\ \Delta \le d_{i,j} + M(1- x_i x_j), \forall i \lt j \\ \sum_i x_i = k\\ x_i \in {0,1}\\ $$ M is an upper bound on the distances: $$ M = \max_{i\le j} d_{i,j}\\ $$ The quadratic part \(x_i x_j\) of the…

Find 10 points out of 50 with maximum distance from each other.¹

This problem can modelled as a max-min model where we maximize the smallest distance of 10 points.

Model

$$ \max \Delta\\ s.t.\\ \Delta \le d_{i,j} + M(1- x_i x_j), \forall i \lt j \\ \sum_i x_i = k\\ x_i \in {0,1}\\ $$

M is an upper bound on the distances: $$ M = \max_{i\le j} d_{i,j}\\ $$

The quadratic part \(x_i x_j\) of the constraint can be linearized:

Read on /dispersion/ ↗