# Integer programming, elimination of products of variables and transfer it to linear integer program

I have a constraint of the form:

$$a_1*a_2 = b_{12}$$

where $$a_1$$ and $$a_2$$ are integer variables with ranges $$a_1∈[{0,1,2,...,m}]$$, $$a_2∈[{0,1,2,...,n}]$$, and $$b_{12}∈[{0,1,2,...,m*n}]$$.

I would want to eliminate the product $$a_1*a_2$$ to make this constraint linear.

If $$a_1$$ and $$a_2$$ do not equal to $$0$$, I can use the $$log(a_1*a_2)= log(b_{12})$$ to convent it into

$$log(a_1) +log(a_2) = log(b_{12})$$, and then use the pre-defined discrete set to transform it into a linear constraitn with binary vectors. such as

$$x_1= log([0,1,2,...,m]) , x_2= log([0,1,2,...,n])$$, and $$y= log([0,1,2,...,m*n])$$.

$$x_1*c1 +x_2*c2 = y*d$$ where $$c_1, c2, d$$ are binary vectors and only one element is 1.

However, as in my model, the feasible set of $$a_1$$ and $$a_2$$ has 0 element. The "$$log$$" trick cannot be used as $$log(0)$$ has no meaning.

It would be a great help if someone could help me out at this.

Thanks a lot.

• What is the connection between $\{a_1, a_2\}$ and $\{x_1, x_2\}$? Mar 6, 2019 at 20:25
• I'm sorry. I made a typo. I have correct this issue. $x_1$ and $x_2$ should be $a_1$ and $a_2$. Do you have any idea? Highly appreciate your help. Mar 7, 2019 at 8:07

If you are willing to use binary expansions, you do not need logs. Using your notation, let $$c_{1,0},\dots, c_{1,m}$$, $$c_{2,0},\dots, c_{2,n}$$ and $$d_0,\dots, d_{m*n}$$ be binary variables, with each set summing to 1. Add the following constraints:$$d_0 \ge c_{1,0}$$$$d_0 \ge c_{2,0}$$and$$d_{j*k}\ge c_{1,j} + c_{2,k} - 1\quad\forall j\ge 1,k\ge 1.$$