Sorting inside a MIP model

This does not happen a lot, but in some cases we want to sort decision variables. This turns out not such an easy exercise.

When not to use sorting

If we deal with just the \(\min()\) or \(\max()\) function we can do things better than sorting. An important trick is to exploit any so-called convexity so we don’t need to add extra binary variables. Even if the problem is not convex, there is no need to sort things.

Interestingly, minimizing the sum of the K largest values also does not need sorting. See (4).

Sorting a parameter

At first sight this is not very useful exercise: we can sort a parameter – constants in the model – outside of the model. However the problem demonstrates some of the concepts I will use later on. Assume \(a_j\) is our given parameter. A permutation \(y\) of \(a\) can be written as \(y=Pa\) where \(P\) is a permutation matrix (1). A permutation matrix is an identity matrix \(I\) with rows and columns interchanged. Such a matrix has exactly a 1 in each row and in each column. A different way to look at this is as an assignment problem with binary variables \(p_{i,j} \in \{0,1\}\).

The linear constraints to sort \(a_j\) (descending) can look like:

\[\boxed{\begin{align} &\sum_i p_{i,j} = 1 \>\> \forall j\\ &\sum_j p_{i,j} = 1 \>\> \forall i\\ &y_i = \sum_j p_{i,j} a_j \\ &y_i \ge y_{i+1} \\ &p_{i,j} \in \{0,1\} \end{align}}\]

Here indices \(i\) and \(j\) are from sets with the same cardinality (\(n\)), i.e. \(p_{i,j}\) is a square matrix. Note that we use \(n^2\) binary variables here, so don’t expect this to work for very large vectors \(a_j\) (2). The same structure can also be used in the context of all-different constraints (3).

Example results

----     32 PARAMETER a  j1 2,    j2 4,    j3 1,    j4 3 ----     32 VARIABLE p.L              j1          j2          j3          j4 i1                       1 i2                                               1 i3           1 i4                                   1 ----     32 VARIABLE y.L  i1 4,    i2 3,    i3 2,    i4 1

Sorting a variable

Instead of sorting a parameter \(a_j\), consider the problem of sorting a variable \(x_j\). We cannot just replace \(a_j\) by \(x_j\) as

\[y_i = \sum_j p_{i,j} x_j \]

is non-linear. There is a way to linearize the product \(q_{i,j} = p_{i,j} x_j\) as this is a multiplication of a binary variable with a continuous variable. Assuming \(x_j \in [0,U_j]\), we have:

\[\begin{align} &0\le q_{i,j} \le U_j p_{i,j}\\ &x_j – U_j (1-p_{i,j}) \le q_{i,j} \le x_j \end{align}\]

Example results

----     41 VARIABLE x.L  j1 0.172,    j2 0.843,    j3 0.550,    j4 0.301 ----     41 VARIABLE p.L              j1          j2          j3          j4 i1                       1 i2                                   1 i3                                               1 i4           1 ----     41 VARIABLE q.L              j1          j2          j3          j4 i1                   0.843 i2                               0.550 i3                                           0.301 i4       0.172 ----     41 VARIABLE y.L  i1 0.843,    i2 0.550,    i3 0.301,    i4 0.172

A different formulation

A different way to formulate a sorting scheme is to look at the problem as a special transportation problem. Transportation equations look like:

\[\boxed{\begin{align} &\sum_i z_{i,j} = x_j \>\> \forall j\\ &\sum_j z_{i,j} = y_i \>\> \forall i \end{align}}\]

As can be seen this is linear in \(x\). We still need to enforce that one supply node is linked to exactly one demand node. This can be done using an additional assignment block:

\[\boxed{\begin{align} &\sum_i p_{i,j} = 1 \>\> \forall j\\ &\sum_j p_{i,j} = 1 \>\> \forall i\\ &\sum_i z_{i,j} = x_j \>\> \forall j\\ &\sum_j z_{i,j} = y_i \>\> \forall i\\ &y_i \ge y_{i+1} \\ &0\le z_{i,j} \le p_{i,j} U_j\\ &p_{i,j} \in \{0,1\} \end{align}}\]

Example results

----     43 VARIABLE x.L  j1 0.172,    j2 0.843,    j3 0.550,    j4 0.301 ----     43 VARIABLE p.L              j1          j2          j3          j4 i1                       1 i2                                   1 i3                                               1 i4           1 ----     43 VARIABLE z.L              j1          j2          j3          j4 i1                   0.843 i2                               0.550 i3                                           0.301 i4       0.172 ----     43 VARIABLE y.L  i1 0.843,    i2 0.550,    i3 0.301,    i4 0.172

Example

From this post:

I'm currently stuck with a MIP program where the interest rate, i, is based on the number of units produced for Housing Plan A. If the number of plan A houses sold is the highest among all four types then i=1. If the number of plan A houses sold is the second highest, then i=2 and so on up to i=4. The interest rate is basically 2i%. Not really sure how to add constraints that will represent the position of plan A houses and implement the correct interest rate in the objective function. The objective function maximizes the total profit (e.g 50,000A + 40,000B + 70,000C + 80,000D). Any ideas on how to use binary variables to represent position?

Some results can look like:

----     47 VARIABLE x.L  A 100.000,    B  90.000,    C 120.000,    D 150.000 ----     47 VARIABLE p.L  permutation matrix             1           2           3           4 A                               1.000 B                                           1.000 C                   1.000 D       1.000 ----     47 VARIABLE q.L  p(i,j)*x(i)             1           2           3           4 A                             100.000 B                                          90.000 C                 120.000 D     150.000 ----     47 VARIABLE xsorted.L  1 150.000,    2 120.000,    3 100.000,    4  90.000 ----     47 VARIABLE r.L  A 0.060,    B 0.080,    C 0.040,    D 0.020

References

1. Permutation Matrix, https://en.wikipedia.org/wiki/Permutation_matrix
2. Sorting by MIP, http://yetanothermathprogrammingconsultant.blogspot.com/2011/10/sorting-by-mip.html, about sorting a parameter
3. All-different and Mixed Integer Programming, http://yetanothermathprogrammingconsultant.blogspot.com/2016/05/all-different-and-mixed-integer.html
4. Paul Rubin, Optimizing Part of the Objective II, http://orinanobworld.blogspot.com/2015/08/optimizingpartoftheobjectivefunction-ii.html