sysid blog · Apr 30, 2023

Select Points

0Sign in to vote or save

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

Given multiple sets of data points. Select one point per set so that the distances between the points is minimal. 1 Model Non-convex MIQP Model $$ \min \sum_{i,j| ok_{i,j}} dist_{i,j} \cdot x_i \cdot x_j \\ \sum_{i|group_{i,g}} x_i = 1 \forall g \\ x_i \in {0,1} $$ Linear MIP Model To linearize the model a standard procedure can be applied: Let’s introduce a new binary variable, $z_{i,j}$,…

Given multiple sets of data points. Select one point per set so that the distances between the points is minimal.¹

Model

Non-convex MIQP Model

$$ \min \sum_{i,j| ok_{i,j}} dist_{i,j} \cdot x_i \cdot x_j \\ \sum_{i|group_{i,g}} x_i = 1 \forall g \\ x_i \in {0,1} $$

Linear MIP Model

To linearize the model a standard procedure can be applied:

Let’s introduce a new binary variable, $z_{i,j}$, that represents the product of the binary variables $\color{darkred}x_i$ and $\color{darkred}x_j$. This new variable will replace the nonlinear term in the objective function, making the model linear. We will also add constraints to link the new variable $z_{i,j}$ with the original variables $\color{darkred}x_i$ and $\color{darkred}x_j$.

Read on /select-points/ ↗

Comments

Nothing yet. Say the first thing.