permutation/ arrangement optimization

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.

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?

• Your example metric function is easily linearizable. What is your real metric function? Jan 14, 2021 at 21:34
• @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$ Jan 15, 2021 at 13:49
• @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 Jan 15, 2021 at 13:53
• $x$ is $(n/N)\times N$, and $d$ is square of size $n/N$ and symmetric? Jan 15, 2021 at 14:03
• @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. Jan 15, 2021 at 21:11

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 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}$$