Linearize a product of an integer variable (not just binary) and a continuous variable?

Question

I have a constraint in my formulation that contains multiplication of an integer variable $y$ and a continuous variable $x$, which is $xy=q$ where $y$ is the number of units in which $q$ gets equally divided to get the quantity $x$ in each unit. Is McCormick envelope a correct way to relax this?

My attempts give me a solution in which the original constraint is violated. Is there any way/algorithm to iteratively update McCormick relaxation for such problems?

I am using Baron 20.4.14 with GAMS. Do I need to include relaxation?

Answer 1

The McCormick envelope is one possible approach. Another, if the domain of $y$ is not too large, is to use a type 1 Special Ordered Set. Assume that $y\in\lbrace 1,\dots,N\rbrace$. Replace $y$ with$$\sum_{j=1}^N j\cdot z_j$$where the $z_j$ are binary variables, and replace the equation $xy=q$ with$$x=\sum_{j=1}^N\frac{q}{j}z_j.$$Add the constraint$$\sum_{j=1}^N z_j = 1.$$ If $q$ is constant, you're done. If $q$ is a variable, you need to do another linearization, replacing $q/j \cdot z_j$ with yet another variable $w_j$ and adding the constraints\begin{align*} w_{j} & \le Qz_{j}\\ w_{j} & \le\frac{q}{j}\\ w_{j} & \ge\frac{q}{j}-\frac{Q}{j}\left(1-z_{j}\right) \end{align*}where $Q$ is an upper bound on $q$.