Deriving order/rank variable from another decision variable

Question

There is a decision variable $x_i$ which denotes the time when a person is allowed to do his work.
The objective function is
$\min (x_i - a_i)$

where $a_i$ is the time when the person arrives at the workplace.
Suppose after solving, the values of decision variable come out to be:

x1 = 10   
x2 = 6  
x3 = 8  
x4 = 3  
x5 = 9

Now I need to formulate an additional objective function and a constraint with another decision variable $r_i$ which denotes the rank or order in which these people start doing the work.
For instance from the above example,

r1 = 5  
r2 = 2  
r3 = 3  
r4 = 1  
r5 = 4 

How do I determine the value of $r_i$ from $x_i$ in the form of a constraint in this multiobjective optimization problem?

Answer 1

Let us introduce binary variables $y_{ij}$ along with the constraint $y_{ij} + y_{ji} \le 1$ for all $i\neq j$. Add the constraints $$x_j - x_i \le My_{ij}\quad \forall i\neq j,$$ where $M$ is an upper bound on the difference between largest and smallest $x$ value. This ensures that $y_{ij}=1$ if $x_j > x_i$. The question does not indicate whether ties in $x$ can happen. With this formulation, if $x_i=x_j$, both $y_{ij}$ and $y_{ji}$ can be either 0 or 1 (though they cannot both be 1).

To compute ranks, we add the constraints $$r_i = 1 + \sum_{j\neq i} y_{ji}\quad \forall i.$$

Assuming starting times are integer-valued, you might want to add $$x_j - x_i \ge 1 - M(1-y_{ij})\quad \forall i\neq j.$$ This eliminates the ambiguity in ties, forcing $y_{ij}=y_{ji}=0$ if $x_i=x_j$.

Answer 2

Your question prompted me to suggest multiple answers, if you would like me to elaborate on one of them please tell me which one in a comment.

• Would be fine with $A_{ij}$ matrix which tells you if $x_i$ is before $x_j$ or otherwise, that would be a lot simpler to implement.
• If you don't have individual constraints on $x_1$, $x_2$ (they can be any employee, not a specific one) you could just enforce an ordering by $x_1 \leq x_2 \leq ... \leq x_5$.
• You could implement a sorting network using a simple to implement gadget that depending on the sign of the difference of it's inputs returns a linear combination of it's inputs such that the lower value is always returned at the lower output.
• You could define a permutation matrix $P$ such that $y = Px$ and $y_1 \leq y_2 \leq ... \leq y_5$ and use that same matrix in $r = P (1,2,3,4,5)^T$. In this case you also want to pose additional constraints on $r$ to cut off useless parts of the search space such as $\sum r = 15$, $1 \leq r_i \leq 5$ and maybe that each integer can only occur once as i am not sure bound tighetening will catch this on it's own.