# linearize bilinear quadratic objective terms

I need to model a problem as a linear program. However my working solution contains a (bilinear) quadratic objective term: $$\sum x_i * y_i \\ x \in \{0,1\} \\ y \in \mathbb{R}^+$$

The value of $$y$$ is calculated in a constraint like this: $$y = \sum\limits_{z \in Z} \sum\limits_{k \in K} f(z,k)$$

Therefore, I tried to move $$x$$ to the calculation of $$y$$ and remodel it to an indicator constraint for avoiding quadratic constraints: \begin{align} x_i = 1 &\rightarrow y = \sum\limits_{z \in Z} \sum\limits_{k \in K} f(z,k) \\ x_i = 0 &\rightarrow y = 0 \end{align}

This solutions eliminates quadratic objective terms. On the other side is the solution gap around 100% and my originale (quadratic) solution archive <1%.

How can I create a stronger formulation for this case?

Edit: Fixed typo of x in equation like mentioned in the comments.

Update: Based on the answer of Erwin Kalvelagen I linearized the quadratic constraint. The resulting performance of my model is not well and the gap is much higher in the same time like the quadratic constraint.
Since I understand from this questions, it is a bilinear/quadratic constraint. What does this mean for my model exactly? Does this have a significant effect to scalability/performance of models in general? Is it possible to say from experience which solution should be preferred (quadratic or linearized (with bigM-Constraint (?)) version)?

• You wrote $x\in(0,1)$, but did you instead mean $x_i\in\{0,1\}$? Also, what other constraints involve $x$? Aug 10, 2022 at 12:26
• It's not clear why the value of $x$ should dictate the value of $y.$ It makes more sense to introduce a new variable $z_i$ to replace $x_i\times y_i$ in the objective and then constrain it so that $x_i=1\implies z_i=y_i$ and $x_i=0\implies z_i=0.$
– prubin
Aug 10, 2022 at 15:16
• @RobPratt: Correct I fixed it.
– Mike
Aug 11, 2022 at 10:20
• @Prubin: I just posted a very small snippet of my model, because I could limit my problem to this constraint. By introducing a new variable and constraint, do you mean something like Erwin Kalvelagen proposed?
– Mike
Aug 11, 2022 at 10:24
• What other constraints involve $x$? In particular, what prevents taking $x_i=0$ for all $i$? Aug 11, 2022 at 12:56

If you know some good bounds, it may be worthwhile to try a formulation with just binary variables. E.g.:

$$\color{darkred}z = \color{darkred}x\cdot \color{darkred}y$$

with $$\color{darkred}x \in \{0,1\}$$ and $$\color{darkred}y \in [0,\color{darkblue}U]$$ can be written as:

\begin{aligned}& \color{darkred}z \le \color{darkred}x \cdot \color{darkblue}U \\ &\color{darkred}z \le \color{darkred}y\\ & \color{darkred}z \ge \color{darkred}y - \color{darkblue}U \cdot(1-\color{darkred}x)\end{aligned}

Sometimes that is faster than indicator constraints (especially if you can find a good, tight $$\color{darkblue}U$$). No guarantee. The real secret behind developing good integer programming models is just to try many things.

• I did implement constraints like you mentioned. I am use to think about U as a bigM value. Right now I did not test a lot a values but my current values slow down my model significant. So is it just about choosing the correct value?
– Mike
Aug 11, 2022 at 10:27
• I choose some values based on this blogpost form prubin orinanobworld.blogspot.com/2011/07/perils-of-big-m.html and calculated for each case an individual value for U (or M) that is the smallest possible value. But the performance (or the gap) is stille not very well compared with the original quadratic constraint. Any better ideas?
– Mike
Aug 11, 2022 at 12:13
• Often, but not always, linear formulations are a bit better, especially after cranking up the cut generation. Aug 11, 2022 at 20:39