1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

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