Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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