Linear Programming - Creating a sequence

Question

I have some numbers in an array and i want to model a LP problem that generates the absolute sequence of the numbers (according to their growing order). For example

input [4,2,1,5] ---> output [3,2,1,4]

That is,if i sort [4,2,1,5], 4 has the third position, 2 is at the second position, and so on.

Can you help me ?

Answer 1

Why is this such a big deal? It's just a few lines of code in any language. Here is a Python version that uses inefficient bubble sort, but it can be modified to use any other sorting algorithm:

def positions(lst):
    n = len(lst)
    index = [i for i in range(0, n)]
    loc = [i + 1 for i in range(0, n)]
    for i in range(0, n - 1):
        for j in range(i + 1, n):
            if lst[i] > lst[j]:
                lst[i], lst[j] = lst[j], lst[i]
                index[i], index[j] = index[j], index[i]
                loc[index[i]], loc[index[j]] = i + 1, j + 1
    return loc

# prints [3,2,1,4]
print(positions([4,2,1,5]))

#prints [6, 3, 1, 4, 5, 7, 8, 9, 10, 2]
print(positions([6,2,0,3,5,7,9,13,15,1]))

Answer 2

Let your sequence be given as $x_{i}$ and introduce binary variables $y_{ik}$ and $z_{ij}$. The following constraints make $y_{ik}$ take the value 1 if $x_i$ is the $k$-th number in the ordered sequence, and make $z_{ij}$ take the value 1 if $x_i \leq x_j$: $$\sum_i y_{ik} = 1 \; \forall k$$ $$\sum_k y_{ik} = 1 \; \forall i$$ $$x_i\leq x_j + M_1(1-z_{ij}) \; \forall i,j$$ $$M_2 z_{ij} \geq \sum_k k y_{jk} - \sum_k k y_{ik} \; \forall i,j$$ Your output list is given by $(\sum_k k y_{ik})_{i=1}^n$. The third constraint enforces $x_i \leq x_j$, unless $z_{ij}=0$. while the last constraint forces $z_{ij}$ to take the value 1 if the ordering position of $x_i$ (which is $\sum_k k y_{ik}$) is less than the ordering position of $x_j$. $M_1$ and $M_2$ are parameters that should be sufficiently large: $M_1$ should be at least the difference between the largest and the smallest $x_i$ and $M_2$ should be at least $n-1$ where $n$ is the number of elements in your list).