Efficient MIP reformulation for binary integer problem

Question

Consider an integer programming model where there is some term $x_ix_j$ where the variables $x_i,x_j \in \{0,1\}$

I want to reformulate this into an efficient mixed-integer programming (MIP) problem.

I can create a new variables $y_{ij}\in R_+$ as a substitute and then add the following constraints:

$y_{ij} \leq x_i \\ y_{ij} \leq x_j \\ y_{ij} \geq 1 - (1-x_i) - (1-x_j)$

I imagine there are various MIP reformulations possible. Is there a more efficient reformulation strategy?

Answer 1

If your optimization function doesn't depend on $y_{ij}$ directly, you may eliminate the last constraint by adding $\epsilon \cdot y_{ij}$ to the objective function (the sign of $\epsilon$ would depend on whether you are maximizing ($\epsilon > 0$) or minimizing ($\epsilon < 0$)).