4

Let's say if I have two decision variables, $f$ and $g$ respectively, where $f$ is continuous, and $g$ is binary.

If I have a constraint like this, $$ f\cdot g \le C$$ Does this make my model nonlinear or quadratic integer model?

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
overboxed
  • 593
  • 1
  • 12
  • 1
    Every quadratic model is also a nonlinear model. Your constraint's left-hand side can be written as a quadratic form, so it's a quadratic model. It's also worth mentioning that you could linearize the constraint, see here. – joni Aug 29 '22 at 05:42
  • So the model will be nonlinear right? What makes it fascinating is that in one of the papers that I'm currently have, they said the formulation is ILP, don't know if typo of something – overboxed Aug 29 '22 at 08:43
  • This constraint, as it is currently written, is non-linear; and more precisely, it is quadratic. But it might be possible to rewrite this constraint into an equivalent linear constraint. In particular, if $f$ is bounded, i.e. you also have a constraint like $A <= f <= B$, then you can rewrite the constraint in a linear way relatively easily: https://cs.stackexchange.com/a/12118/127905 – Stef Aug 29 '22 at 16:05

1 Answers1

4

Your model is linear if and only if your objective function and the functions on the left hand side of your constraints (assuming only constants are left on your right hand side) are linear and the variables may take values in $\mathbb{R}$. If it is not linear, then it is non-linear (which comes in many flavours!)

Your function on the LHS of your constraints is $h(f,g)=f\cdot g$, which is not linear as $h(\alpha f,\alpha g) = \alpha h(f,g)$ is not true for all $\alpha \in \mathbb{R}$.

Sune
  • 6,457
  • 2
  • 17
  • 31
  • 5
    If everything else is linear, and as pointed out by @jon , $f*g$ can be linearized, thereby converting the entire model into a MILP, which reconciles with the claim in the paper. – Mark L. Stone Aug 29 '22 at 14:32