Linearize non-linear constraint 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.

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.