2
$\begingroup$

I would like to obtain the optimized arrangement of integers. Let me give a simple example.

Suppose I have a sequence like 1,2,3,4,5 I would like to re-arrange it according to a given metric function. Suppose in this case, the metric function is $g(x)$ where $g(x) = \min(|x_{i+1}-x_i|)$. So in our case, $g(x) = \min(\{2-1, 3-2, 4-3, 5-4\}) = 1$

if we have $x = \{2,5,3,1,4\}\implies g(x) = \min(\{|5-2|, |3-5|, |1-3|, |4-1|\}) = \min(\{3,2,2,3\})=2$

Now Suppose we want to re-arrage the vector such that we maximize this metric function, how can we formulate the problem? Is there a way to solve this without trying all permutations? In my problem, I have a vector of length n and a different metric function which is quite complicated than the one given above.

Let me know if more information is needed

EDIT:

We could think of the problem as $$\underset{x}{\arg\max} ~g(x)~~s.t.~ x_i\in \mathbb N, \mathbf{x} = \{1,...,N\}$$

Can this work? If so how can we proceed?

$\endgroup$
7
  • 1
    $\begingroup$ Your example metric function is easily linearizable. What is your real metric function? $\endgroup$ – RobPratt Jan 14 at 21:34
  • $\begingroup$ @RobPratt the metric i have is the manhattan distance between the points. ie, $x$ is a vector which given a parameter N, you can write it in a column major format and take the manhattan distances of the points, then obtain the minimum of those distances. eg. if $x=\{1,2,3,4,5,6\}$ and $N=2$ then we have $x = \begin{pmatrix}1&4\\2&5\\3&6\end{pmatrix}$ and then compute the manhattan distance $d(x) = \begin{array}{c|ccc}&1&2&3\\\hline1&0&2&4\\2&2&0&2\\3&4&2&0\end{array}$. Then ignoring the diagonal, I look for the minimum ie 2. Thus $g(x)=2, \quad\text{given } ~N=2$ $\endgroup$ – Onyambu Jan 15 at 13:49
  • $\begingroup$ @RobPratt the aim is to use any distance metric function really. instead of manhattan distance, look at the euclidean distance, for example. Hope this helps $\endgroup$ – Onyambu Jan 15 at 13:53
  • $\begingroup$ $x$ is $(n/N)\times N$, and $d$ is square of size $n/N$ and symmetric? $\endgroup$ – RobPratt Jan 15 at 14:03
  • $\begingroup$ @RobPratt yes $x$ is $n\times N$ vector and $d$ is always symmetric. Only interested in the monimum distance in d. So whether you compute only the lower or upper triangle is fine. The metric function $g(x)=\min d(x)$. The aim is to rearrange $x$ such that $g(x)$ is maximized. $\endgroup$ – Onyambu Jan 15 at 21:11
2
$\begingroup$

You can solve the problem via mixed integer nonlinear programming as follows. Let $m$ be the number of rows and $n$ the number of columns. For $i\in \{1,\dots,m\}$, $j\in \{1,\dots,n\}$, and $k\in \{1,\dots,mn\}$, let binary decision variable $y_{i,j,k}$ indicate whether $x_{i,j}=k$. Let $z$ represent the minimum distance over row pairs $(i_1,i_2)$. The problem is to maximize $z$ subject to \begin{align} \sum_k y_{i,j,k} &= 1 &&\text{for all $i,j$} \tag1 \\ \sum_{i,j} y_{i,j,k} &= 1 &&\text{for all $k$} \tag2 \\ \sum_k k y_{i,j,k} &= x_{i,j} &&\text{for all $i,j$} \tag3 \\ z &\le \sum_j |x_{i_1,j}-x_{i_2,j}| &&\text{for all $i_1,i_2$ with $i_1<i_2$} \tag4 \\ \end{align} Constraint $(1)$ assigns exactly one value per cell. Constraint $(2)$ assigns exactly one cell per value. Constraint $(3)$ enforces $y_{i,j,k}=1 \iff x_{i,j}=k$. Constraint $(4)$ enforces the maximin objective; you can replace the right-hand side with any distance formula for row pairs.

For $m=3$ and $n=2$, here is an optimal solution, with $z=|6-5|+|4-2|=3$: $$ x = \begin{pmatrix} 1 &3 \\ 6 &4 \\ 5 &2 \\ \end{pmatrix} $$

$\endgroup$
1
  • $\begingroup$ Thanks so much for taking your time to do this. I will definitely accept this as a solution. In the meantime, could you please provide some links/boks to rwad on this kind of maximization? I would appreciate $\endgroup$ – Onyambu Jan 16 at 17:48

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.