# Optimization problems containing binary variable

#1

x is binary, 0=< y <=K, Z is their product. The transformation is z≥0, z≤y, z≤Kx, y−z≤K(1−x)

Is the transformation of the multiplication of two variables correct? I have tried the method ,but it seems that it is not right. The optimization problem becomes unbounded.

if x equals 0, then

``````z>=0 z<=y z<=0 y-z <= K
-> Z = 0, 0<= y <= K
``````

if x equals 1, then

``````z>=0 z<=y z<=K y-z <=0
-> z = y
``````

It is correct, but when adding the constraints to the problem it gets unbounded. In the following, T = X * S.

``````K = 10;

cvx_begin
variable X(3);
variable Y(3);
variable Z(3);
variable T(3);
variable S(3) binary;
minimize(sum(Z));
subject to
{T,1000*Y,Z} == exponential(3);
X>=0;
X<=K;
Y>=1e-10;
Y<=1;
sum(Y) <= 1;

% transformation
T >= 0; T <= X;
T <= K.*S;
X - T <= K.*(1-S);

sum(T) >= 5;
sum(S) <= 2;
cvx_end
``````

Using Mosek to solve this problem, it gives the result of unbounded.

(Michael C. Grant) #2

I’ll be honest, I have no idea what the consequences are of using the exponential cone (and, therefore, CVX’s successive approximation method) with binary variables. I would not be surprised if it does not work at all.

(Michael C. Grant) #3

I hate to do this to you, but I’m afraid that binary variables and exponential cones don’t mix. The successive approximation approach is going to be confused by the branching methods employed by MOSEK’s binary solver. In a future update of CVX I am going to have to detect and reject this particular combination of constraints.

#4

All right, I am going to search if there is some other way to solve this problem. Once solved, I will share the solution.

Unbounded model with binary variable and exp constraint
CVX reports unbounded status but with viable solution

Hello Michael, I want the result as of XNOR logic gates from two binary variables, how can I use these two binary variables to get the requires results?

(Mark L. Stone) #6

Please don’t keep posting the same question in thread after thread. As I posted a couple of your same questions ago, the solution for XOR s provided in the XOR paragraph of the first answer at https://cs.stackexchange.com/questions/12102/express-boolean-logic-operations-in-zero-one-integer-linear-programming-ilp . If you negate the output y_5 in that answer, which is achieved by substituting 1-y_5 for y_5, you will have the solution for XNOR.