Optimization problems containing binary variable


#1

Transformation reference)

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