4
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – joni
    Commented Aug 29, 2022 at 5:42
  • $\begingroup$ 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 $\endgroup$
    – overboxed
    Commented Aug 29, 2022 at 8:43
  • $\begingroup$ 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: cs.stackexchange.com/a/12118/127905 $\endgroup$
    – Stef
    Commented Aug 29, 2022 at 16:05

1 Answer 1

4
$\begingroup$

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}$.

$\endgroup$
1
  • 5
    $\begingroup$ 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. $\endgroup$ Commented Aug 29, 2022 at 14:32

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.