# How do you take into account order in linear programming?

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?

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

• One trick that sometimes works in these scenarios is also that you can prune combinations of #i and #k when you are defining the variables. In some cases, this reduces the number of variables to be passed to the solver considerably. – Richard Jan 8 at 8:01

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

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

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