Linearize non-linear constraint

Question

I have a problem which may be defined as:

$$\max 5 x_{11} + 6 x_{12} + 2 x_{21} + 3 x_{22} \\ x_{ij}\in \{0,1\} \\ x_{11} + x_{12} = 1 \\ x_{21} + x_{22} = 1 \\ t_1,t_2 \text { integer} \\ (t_1 - t_2) x_1 x_2 \ge 0$$

I want to check $t_1-t_2 \ge 0$ only if $x_{11} = x_{21} = 1$.

How can I linearize this constraint? Or is it possible to linearize it?

Thank you very much.

Answer 1

You can linearize it as follows: $$ t_2-t_1\le M(2-x_{11}-x_{21}) $$ where $M$ is a large constant.

Indeed, if $x_{11}=x_{21}=1$, the right hand term equals $0$, therefore $$ t_2\le t_1, $$ Otherwise the constraint is equivalent to $$ t_2\le t_1+M, $$ which is always true provided $M$ is large enough.