Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer


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.