2
$\begingroup$

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)?

$\endgroup$
8
  • 1
    $\begingroup$ You wrote $x\in(0,1)$, but did you instead mean $x_i\in\{0,1\}$? Also, what other constraints involve $x$? $\endgroup$
    – RobPratt
    Commented Aug 10, 2022 at 12:26
  • 1
    $\begingroup$ 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.$ $\endgroup$
    – prubin
    Commented Aug 10, 2022 at 15:16
  • $\begingroup$ @RobPratt: Correct I fixed it. $\endgroup$
    – Mike
    Commented Aug 11, 2022 at 10:20
  • $\begingroup$ @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? $\endgroup$
    – Mike
    Commented Aug 11, 2022 at 10:24
  • $\begingroup$ What other constraints involve $x$? In particular, what prevents taking $x_i=0$ for all $i$? $\endgroup$
    – RobPratt
    Commented Aug 11, 2022 at 12:56

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Mike
    Commented Aug 11, 2022 at 10:27
  • $\begingroup$ 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? $\endgroup$
    – Mike
    Commented Aug 11, 2022 at 12:13
  • $\begingroup$ Often, but not always, linear formulations are a bit better, especially after cranking up the cut generation. $\endgroup$ Commented Aug 11, 2022 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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