0

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 ?

Jhdoe
  • 215
  • this is impossible without adding binary variables – LinAlg Dec 27 '18 at 23:48
  • Okay, can you show me the model with the introduction of the binary variables ? – Jhdoe Dec 28 '18 at 07:31
  • Why do you want to use linear programming for this task? – littleO Dec 28 '18 at 08:06
  • Qoute from Wikipedia: "LP is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships". I might be stupid but I don't see any connection between this problem and LP. – Saša Dec 28 '18 at 08:23
  • It's for didactic reasons. I would like to know if it's possible to do it... – Jhdoe Dec 28 '18 at 11:53
  • LP is about achieving optimal result with a set of linear constraints in place. What are the linear constraints in your problem? – Saša Dec 28 '18 at 13:12
  • did you appreciate my answer? – LinAlg Jan 08 '19 at 15:04

2 Answers2

0

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]))
Saša
  • 15,906
0

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).

LinAlg
  • 19,822