5
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Richard Jan 8 at 8:01
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.