## Saturday, December 10, 2016

### 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                       1i2                                               1i3           1i4                                   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                       1i2                                   1i3                                               1i4           1 ----     41 VARIABLE q.L              j1          j2          j3          j4 i1                   0.843i2                               0.550i3                                           0.301i4       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                       1i2                                   1i3                                               1i4           1 ----     43 VARIABLE z.L              j1          j2          j3          j4 i1                   0.843i2                               0.550i3                                           0.301i4       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.000B                                           1.000C                   1.000D       1.000 ----     47 VARIABLE q.L  p(i,j)*x(i)             1           2           3           4 A                             100.000B                                          90.000C                 120.000D     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

1. Hi Erwin,

Thanks for this. Very useful.

Do you have any suggestions on how to sort large numbers of decision variables? Say n = 10k upwards.
z and p will obviously get big with n squared. While memory isn't such a constraint these days, large z and p decision variables would, I think, slow problem setup and solve

Bye for now

David

2. Is the transportation equations formulation more efficient for sorting variables?

1. I would say: Try it out on your model with your data.