4
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – A.Omidi
    Oct 27 at 14:20
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Oct 27 at 15:47
  • $\begingroup$ I am really thankful for this solution. I was able to model the ranks successfully. $\endgroup$ Nov 11 at 7:34
1
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.