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

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?

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.

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

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.

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!)

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.

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?

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.

1 Like
9

I have one question, please. We use section 2.8 to linearized the product of binary and continuous variables if the product exists in the constraints. What if the product exists in the objective function itself?

Thanks!

10

If you have a product y = x*d for one continuous variable x and one binary variable d, you should use y in place of x*d, whether x*d occurs in the objective function, in the constraints, or both. Whether x*d appears in the objective function, in the constraints, or both, you need to add the constraints in section 2.8

1 Like
12

That is really helpful.
But still, in my objective function, it is like objective=xd+max(x)
if I assume y=xd, my objective will by objective=y+max(y/d)
now I will have an issue that y/d need be liberalized.
I do not know if I still have a chance to linearize it. If I choose to normalize y/d by assuming z=y/d my new objective will be objective=d*z+max(z) which is the initial problem.

Thanks

13

x is and should be declared to be a CVX variable. You can keep x as is in your program. As seen in 2.8 of the link, x appears in the constraints which are added as part of the linearization.

1 Like
14

Thank you. Which solver should I use to solve the problem since I have binary and continuous? is it the MOSEK solver?

Thanks

15

Mosek or Gurobi, unless there are 3 by 3 or higher dimensional SDP constraints, in which case Mosek is the only suitable solver. http://cvxr.com/cvx/doc/solver.html#supported-solvers

1 Like
16

Thank you so much to facilitate my research.
Your comments were really helpful.

I am just kind of curious why SDPT3 provides a smoother profile than MOSEK if used for the same problem (see the attached figure). However, both of them solve my problem with the minimal objective. (u in the figure is the CVX variable)

solvers_differences
solvers_differences840×630 12.9 KB

17

SDPT3 doesn’t support binary or integer variables, so I don’t even know what problem you are solving with it.