Gurobi doesn't works for quadratic cost

[Yi-Wen Liao]

Hello Johan,

I need some helps for using Gurobi to solve mix-integer programming. 

I don't know why that when I set my cost as a linear function, I can get the solution from Yalmip. But if I change the cost into quadratic form then it is not working anymore.

Thank you,

Grace  

[Johan Löfberg]

Most likely you've defined a nonconvex quadratic function. Gurobi only works for convex quadratics (if it only has binary variables, you can easily transform it to a convex quadratic)

[Yi-Wen Liao]

Hello Johan,

Thank you so much for the replying. But I did have convex quadratic cost function. The binary variables only occur in the constraints.

I past my partial code here.

epsilon = sdpvar(1,1);

uk = sdpvar(2,N);

duk = sdpvar(2,N-1);

xk = sdpvar(6,N);

z1k = binvar(1,4);

z2k = binvar(1,4);

cost = (xk(:,N)-xDesire(:,N))'*Q*(xk(:,N)-xDesire(:,N))+q*epsilon;

constr = [xk(:,1)==x0, uk(:,N)==u0, epsilon >= 0, ...

     uk(:,1)==uk(:,N)+duk(:,N-1), ...

     duk(1,N-1) <= 1.5, duk(1,N-1) >= -1.5, duk(2,N-1) <= 0.8, duk(2,N-1) >= -0.8];

for i=1:N

    if i < N

    cost = cost + (xk(:,i)-xDesire(:,i))'*Q*(xk(:,i)-xDesire(:,i))+uk(:,i)'*R*uk(:,i)+duk(:,i)'*duk(:,i);

    constr = constr+ [...

            xk(1,i+1) == xk(1,i)+2*(a+b)*mu*Fzf*uk(2,i)*dt/(m*b)-xk(3,i)*v0*dt, ...

            xk(2,i+1) == xk(2,i)+2*mu*Fzf*uk(1,i)*dt/m, ...

            xk(3,i+1) == xk(3,i)+2*a*mu*Fzf*uk(2,i)*dt/I-2*b*Cr*xk(1,i)*dt/(I*v0)+2*b*Cr*(b+p)*xk(3,i)*dt/(I*v0), ...

            xk(4,i+1) == xk(4,i)+xk(3,i)*dt,...

            xk(5,i+1) == xk(5,i)+v0*xk(4,i)*dt+(xk(1,i)-p*xk(3,i))*dt, ...

            xk(6,i+1) == xk(6,i)+xk(2,i)*dt, ...

            Hu*uk(:,i) <= Ku ...

            Hx*xk(5,i) <= Kx,...

            ];

    end

    if i < N-1

       constr = constr+ [...

          uk(1,i+1) == uk(1,i)+duk(1,i), ...

          uk(2,i+1) == uk(2,i)+duk(2,i), ...

          duk(1,i) <= 1.5, duk(1,i) >= -1.5, ...

          duk(2,i) <= 0.8, duk(2,i) >= -0.8, ...

          ];

    end

    

    if (i >= k(1)) && (i <= k(1)+1)

          constr = constr+ [xk(6,i) < aheadPoint(1)+32*z1k(i-k(1)+1), ...

                    -xk(5,i)+leftWidth<=32*z2k(i-k(1)+1)+32*(1-z1k(i-k(1)+1))+epsilon, ...

                    xk(5,i)+rightWidth<=32*(1-z2k(i-k(1)+1))+32*(1-z1k(i-k(1)+1))+epsilon];

    elseif (i > k(1)+1) && (i < k(2))

          constr = constr+ [-xk(5,i)+leftWidth<=30*z2k(2)+epsilon, ...

                    xk(5,i)+rightWidth<=30*(1-z2k(2))+epsilon];

    elseif (i >= k(2)) && (i <= k(2)+1)

          constr = constr+ [-xk(6,i)<-aheadPoint(2)+32*z1k(i-k(2)+3), ...

                    -xk(5,i)+leftWidth<=32*z2k(2)+32*(1-z1k(i-k(2)+3))+epsilon, ...

                    xk(5,i)+rightWidth<=32*(1-z2k(2))+32*(1-z1k(i-k(2)+3))+epsilon];

    end     

end

This code can be solved by BMIBNB solver, but won't work for Gurobi. 

[Yi-Wen Liao]

Or I use the following simple code to test the solver:

z1k = binvar(1,4);

xk = sdpvar(1,2);

cost = xk(1,1)+2*xk(1,2);

constr = [z1k(1,1)>= 1, z1k(1,2) ==0, xk(1,1)>=1, xk(1,2)>=-1];

The matlab shows:

Gurobi Mex Version 1.61. Gurobi Library Version 6.0.3.

??? Unknown option field: LPMethod ???

Optimize a model with 4 rows, 4 columns and 4 nonzeros

Coefficient statistics:

  Matrix range    [1e+00, 1e+00]

  Objective range [1e+00, 2e+00]

  Bounds range    [1e+00, 1e+00]

  RHS range       [1e+00, 1e+00]

Found heuristic solution: objective -1

Presolve removed 4 rows and 4 columns

Presolve time: 0.00s

Explored 0 nodes (0 simplex iterations) in 0.01 seconds

Thread count was 1 (of 4 available processors)

However, if I change the cost function into:

z1k = binvar(1,4);

xk = sdpvar(1,2);

cost = xk(1,1)^2+2*xk(1,2);

constr = [z1k(1,1)>= 1, z1k(1,2) ==0, xk(1,1)>=1, xk(1,2)>=-1];

Then, it won't work.

[Johan Löfberg]

Since I don't have the data, I cannot run your code or check the matrix Q

My only guess is that the problem becomes numerically indefinite, in the same sense that the following expression indicates indefiniteness for a theoretically psd matrix

 min(eig(ones(10,1)*ones(1,10)))

One way to improve this is to introduce new variables for the terms in the quadratic

...
e = sdpvar(n,1)
constraints = [constraints, e == chol(Q)*(xk(:,i)-xDesire)]
objective = objective +  e'*e

[Johan Löfberg]

YALMIP does not support Gurobi Mex. You should use Gurobis own MATLAB interface.

[Yi-Wen Liao]

Oh. I see. 

Probably because I didn't use Gurobi's own MATLAB interface. I use Gurobi Mex.

Thank you so much.

[Yi-Wen Liao]

Hello Johan,

I delete the path of Gurobi Mex and connect Gurobi's own interface but still cannot run the simple code of:

z1k = binvar(1,4);

xk = sdpvar(1,2);

cost = xk(1,1)^2+2*xk(1,2)+z1k(1,1);

constr = [z1k(1,1)>= 1, z1k(1,2) ==0, xk(1,1)>=3, xk(1,2)>=-1];

options = sdpsettings('solver','gurobi');

solvesdp(constr,cost,options);

It shows up the information of "Solver not applicable (gurobi)"

However, If I delete the square term in the cost function (like the code shown below), Gurobi will give out the solution.

z1k = binvar(1,4);

xk = sdpvar(1,2);

cost = xk(1,1)+2*xk(1,2)+z1k(1,1);

constr = [z1k(1,1)>= 1, z1k(1,2) ==0, xk(1,1)>=3, xk(1,2)>=-1];

options = sdpsettings('solver','gurobi');

solvesdp(constr,cost,options);

[Johan Löfberg]

You must have a very old version of YALMIP

[Yi-Wen Liao]

Thank you. I update the YALMIP and problem solved.^^