# Deriving order/rank variable from another decision variable

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?

• Would you say please, actually, what is the difference between $x_{i}$ and $r_{i}$? Based on what you mentioned, both of them can be translated as the start time of work $i$!? What does exactly the rank/order mean? That it presumably should be defined as a boolean variable. Oct 27 at 14:20

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

• Wow, this is a lot more elegant than what i have suggested. @Adnan pick this answer. It's so obvious looking back. If there are 3 people which become before you, you are 4th. Oct 27 at 15:47
• I am really thankful for this solution. I was able to model the ranks successfully. Nov 11 at 7:34

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.