Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
I have a problem with a nonlinear constraint. The non-linearity stems from a term of the form $xb$, where $x \in \mathbb{R}^+$, $x < M$ and $b \in \{0, 1\}$. I am able to remove this non-linearity by using McCormick envelopes.
If I solve the problem using this relaxation, am I actually solving the problem or am I just finding a very tight lower bound?. Remember that one of the variables is binary.
What if $b \in \mathbb{N}$ instead?
For real $x\in[l,u]$ and binary $b\in\{0,1\}$ the McCormick envelope gives you bounds on $w=xy$
$$\begin{align} lb & \leq w \leq ub,\\ ub+x-u& \leq w\leq x+lb-l. \end{align}$$
By case analysis you can see that this is equal to $w=xb$, so you will indeed solve the problem.
