 How can I fix this issue: multiplication of binary and continuous variables?

(Dipak Narayanan) #1

I have an optimization problem that has a constraint

x_m=\sum_{n=1}^Nb_{n,m}c_{n,m}d_{n,m},m=1,2,\cdots,M

Here, b_{n,m} is a binary variable and c_{n,m} is a continuous variable
d_{n,m} are given.

I linearize the multiplication of binary and continuous variable b_{n,m}c_{n,m} by introducing a new variable p_{n,m}=b_{n,m}c_{n,m} and then adding the follwing linear constraints

(i) p_{n,m}\le b_{n,m}
(ii) p_{n,m}\ge 0
(iii) p_{n,m}\le c_{n,m}
(iv) p_{n,m}\ge c_{n,m}-(1-b_{n,m})

since c_{n,m} is lower and upper bounded by 0 and 1, respectively.

ISSUE:

I have other constraint as
\sum_{n=1}^Nb_{n,m}\le 2, m=1,2, \cdots,M

and

\sum_{m=1}^Mc_{n,m}\le 1, n=1,2, \cdots,N

I expected that after we solve the problem, if the output p_{n,m}>0, I have b_{n,m}=1, but this is not the case. I have noticed that for some p_{n,m}>0, I have b_{n,m}=0 or vice versa. The same goes for c_{n,m}.

Why is that happening and how can I fix this?

(Mark L. Stone) #2

It appears that you have not correctly implemented the linearization of the product of a continuous variable and a binary variable in the first case of section 2.8 of https://www.fico.com/en/resource-download-file/3217 . Please study that formulation and convince yourself it is correct. Then fix your won formulation. Per what you write, your L = 0 and your U = 1.

(Dipak Narayanan) #3

@Mark_L_Stone, Unfortunately, to me , it seems that the formulation is inline with the MIP formulation proposed in section 2.8 of the referenced document. I would request you to pinpoint where and what went wrong.

(Mark L. Stone) #4

On reexamining your formulation, it looks correct.

Foist of all, are you getting these results with status of Solved? Perhaps there are numerical tolerance issues? How much greater than 0 are the cases in which p > 0 but b does not equal 1? p can be slightly greater than 0 and b slightly less than 1 (but not zero) and still be considered to satisfy p <= b.

(Dipak Narayanan) #5

@Mark_L_Stone, Thanks for your remarks. Regarding the solve status I have the following message:

Optimal solution found (tolerance 1.00e-04)

Warning: max bound violation (2.0452e-08) exceeds tolerance

Best objective -9.526544925580e-01, best bound -9.526544925580e-01, gap 0.0000%

------------------------------------------------------------

Status: Solved

Optimal value (cvx_optval): +0.952654


I have checked the results thoroughly and I have found that

for ALL the cases with p>0, I have b=1 (Expected)

but for some cases with p=0, I have b=1 (Not expected!)

(Mark L. Stone) #6

If p = 0 and b = 1, then it should be the case that c = 0 (within solver tolerance). That satisfies all constraints and is consistent with the relationship you linearized, p = b*c.

You did not implement iff logic, which is different, nor is it appropriate for p = b*c.

(Dipak Narayanan) #7

@Mark_L_Stone, There is no way for resolving this? Can we use "if a==1, f>0" or "if p==0, a=0", etc?

(Mark L. Stone) #8

I don’t know what you want to resolve. You have lineasrized the product.

If you actually want an if and only if, then you can implement the appropriate constraints to do so. But that would be doing something different than linearizing the constraint. It would be overconstraining the linearization, with the possibility (depending on the rest of the problem) of producing a suboptimal solution to what I thought was your original problem.

It is your problem, so you can make it whatever you want it to be.