How do you take into account order in linear programming?

Question

How do you write order in a linear program?

For instance, you want to arrange red and blue marbles labelled 1 – 30 each, and you would want to arrange it in ascending order, you cannot have red marble #28 before #7 - how do you communicate that through LP?

Answer 1

Presumably you have binary decision variables like $x_{ik} = 1$ if marble #$i$ is in slot #$k$. Then you can write a constraint like

$$x_{ik} \le 1 - x_{jl} \qquad \forall \text{$i < j$ and $k > l$}$$

In other words, if $i < j$ and $j$ is in slot $l$, then $i$ cannot be in any slot $k$ that comes after $l$.

Answer 2

As per the answer by @LarrySnyder610, we can use position-based variable $x_{ik}$ to model such scenarios. Note that we also need the following constraints to ensure that each $i$ is assigned to exactly one position $k$: $$ \sum_{k}x_{ik}=1 ~~~~~~~~ \forall i $$ If $n$ is the total number of possible $i$ or $k$, then this method requires $\mathcal{O}(n^4)$ constraints. Another way to model this is to introduce auxiliary variables $p_i$ to capture the position number of $i$. In this case, we can use the following constraints to achieve the same result: $$ \sum_{k}x_{ik}=1 ~~~~~~~~ \forall i\\ \sum_{k}kx_{ik}=p_i ~~~~~~~~ \forall i\\ p_i \le p_{i+1} ~~~~~~~~ \forall i<n. $$

In this case, the order of the constraints is reduced to $\mathcal{O}(n)$. In addition, the number of non-zero elements of the coefficient matrix is reduced which could result in faster LP-relaxation solutions. Such application of the auxiliary variables has been shown to be effective in some cases (see e.g., here and here).

Answer 3

Considering you have a set of n variables (elements) $p_1, p_2, …, p_n$ to be sorted in ascending order so that $p_{[1]}, p_{[2]}, …, p_{[n]}$

where $p_{[1]} \leq p_{[2]} \leq …\leq p_{[n]}$,

you can introduce $n^2$ binary decision variable $ x_{i,j}$ and $n$ variables $A_i$.

$ x_{i,j}=1$ if $i-th$ element is assigned to $j-th$ position.

$ min \left \{ \sum_{i = 1}^n A_i \right \} $

Subject to

:$ \left\{ \begin{array}{l} A_1 = \sum_{i=1}^n x_{i,1} \cdot \ p_{i} \\ A_2 = A_1 + \sum_{i=1}^n x_{i,2} \cdot \ p_{i} \\ \vdots \\ A_n = A_{n-1} + \sum_{i=1}^n x_{i,n} \cdot \ p_{i} \\ \sum_{i=1}^n x_{i,k} = 1 \forall \ k \\ \sum_{k=1}^n x_{i,k} = 1 \forall \ i \\ A_i \ge 0 \forall \ i \\ x_{i,k} \in \left \{ 0 ; 1 \right \} \forall \ i, k \end{array} \right.$

What it has been written works for example in one machine scheduling problem where $p_1, p_2, …, p_n$ represent processing times.

For example: the set $p_1=16.2, p_2=16, p3=16.1 , p_4=15.9, p_5=15.7, p_6=15.8 $ is easily ordered by the model as $p_{[1]}=15.7, p_{[2]}=15.8, …, p_{[6]}=16.2$

The element in first position is equal to $p_{[1]} = \sum_{i=1}^n x_{i,1} \cdot \ p_{i}$

The element in second position is equal to $p_{[2]} = \sum_{i=1}^n x_{i,2} \cdot \ p_{i}$

The element in third position is equal to $p_{[3]} = \sum_{i=1}^n x_{i,3} \cdot \ p_{i}$ ...

Remark

If you wish to sort in descending order the set, it is sufficient to consider $ max \left \{ \sum_{i = 1}^n A_i \right \} $.