Mixed Integer Linear Programming for a Ranking Constraint

Question

I am trying to write a mixed integer linear programming for a constraint related to the rank of a specific variable, as follows:

• I have X1, X2, X3, X4 as decision variables.
• There is a constraint asking to define i as a rank of X1 (For example, if X1 is the largest number amongst X1, X2, X3, X4, then i=1; if X1 is the second largest number then i=2, if X1 is the 3rd largest number then i=3, else i=4)

How could I write this constraint into a mixed integer linear programming?

Answer 1

Not so easy. Here is an attempt:

First introduce binary variables y(i) for i=2,3,4

Then we can write:

 x(1) >= x(i) - (1-y(i))*M   i=2,3,4
 x(1) <= x(i) + y(i)*M       i=2,3,4
 rank = 4 - sum(i,y(i))
 y(i) ∈ {0,1}                i=2,3,4

Here M is a large enough constant (a good choice is the maximum range of the data). If your solver supports indicator constraints, you can simplify things a bit.

A small example illustrates it works:

----     36 VARIABLE x.L  

i1 6.302,    i2 8.478,    i3 3.077,    i4 6.992


----     36 VARIABLE y.L  

i3 1.000


----     36 VARIABLE rank.L                =            3.000