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


(Quentin_EE) #1

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 and use the CVX mosek solver to solve the MILP.

If x_1 and x_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.


(Mark L. Stone) #2

You can introduce enough binary variables to do binary encodings of the integer variables. Then do the standard linearization for products of binary variables.