permutation/ arrangement optimization

Question

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?

Answer 1

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