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?
$\begingroup$
$\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$– joniAug 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$– overboxedAug 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$– StefAug 29, 2022 at 16:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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}$.
-
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$ Aug 29, 2022 at 14:32