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?


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


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.