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 Answer 1

Reset to default
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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.