How do I exploit a good initial guess of the optimal solution?

[sebbesen]

Hi,

I am able to generate a very reasonable guess of the optimal solution to my mixed integer QP prior to actually invoking the solver (Gurobi, CPLEX). I am wondering how I can exploit this? I've noticed that there is an option called 'usex0' (I suppose this means "use x0" where x0 is an initial guess). However, the documentation is a bit brief on this topic. In particular, I don't understand how I pass my initial guess, say x0, to the solver? All I can do is to set usex0 = 1, but how do I define the actual initial guess?

Thanks,

Søren

[sebbesen]

I figured it out: use assign to set the initial values of your variables. I was expecting a significant improvement in the time taken to solve my problem, in particular due to the presence of three binary variables. However, specifying a good initial guess didn't seem to improve anything for my problem. Any comments would be appreciated.

Thanks,

Søren

[Johan Löfberg]

Exactly, assign followed by the usex0 option.

There are a couple of issues here. To begin with, are all your variables really assigned? If you have a high-level model where YALMIP has to introduce internal variables to represent various complex expressions, these variables will not be assigned, hence the solver doesn't really have an initial guess (as many of the guessed values will have default value 0, and thus the guess is not feasible)

Assuming though that you have a simple model where all variables are defined and assigned by you, you might still have problems. If you use gurobi, YALMIP does not send any initial guess, since the standard MATLAB interface supplied by Gurobi doesn't seem to support this. At least I haven't found the way to do it. The third-party interface gurobi_mex supports this though, and if you use this from YALMIP I send the initial guess. However, I have not used gurobi_mex though since gurobi started shipping with a matlab interface. Cplex claims to support an initial guess, and I send an initial guess, but when I look at the output displayed by cplex, I cannot see any trace of my initial guess (the upper bound in the first number of iterations reported by cplex is worse than the solution I send). I will investigate this further

Having said that, an initial guess, i.e., an upper bound, does not help much most often. In many cases, the solver rapidly finds a very good solution anyway, and the problem is to close the gap, i.e., generating efficient lower bounds.

n = 40;

S = randn(n);S = S*S'/1000; % Covariance

mu  = rand(1,n)/100;        % Expected return

mutarget = mean(mu);

w = sdpvar(n,1);

d = binvar(n,1);           % models if variable is nonzero

F = [sum(w) == 1, 1>=w>=0, mu*w == mutarget];

F = F + [sum(d) <= 10]   % At most 10 positions

F = F + [w <= d];       % If d==0 then w = 0

F = F + [w >= 0.1*d];   % If d==1 then w >= 0.1

F = F + [w <= 0.8];     % No position >= 0.8

solvesdp(F,w'*S*w,sdpsettings('solver','cplex'))

% Optimal objective

double(w'*S*w)

% resolve with optimal solution as initial guess

% already assigned since it is the current value
% The value above should be shown as Best integer already
% in node 0 if it actually uses the solution

solvesdp(F,w'*S*w,sdpsettings('solver','cplex','usex0',1))

[sebbesen]

Thank you for your answer - I see what you mean. The fact that the proprietary Gurobi interface does not support an initial guess explains a lot. Maybe YALMIP could issue a warning if the user-specified initial guess is neglected by the chosen solver. I might try installing gurobi_mex again. Is there a way to tell YALMIP to use the third-party interface if both are in the search path?

[Johan Löfberg]

Good idea with the warning.

I think the solver specification 'gurobi-mex' should work

[sebbesen]

OK, will try that. Thanks again, and best regards from ETH.

[Johan Löfberg]

Let me know if initial guesses works as expected with gurobi-mex.

[sebbesen]

I'm getting "Solver not applicable (gurobi-mex)" in diagnostics.info. I'm suspecting gurobi_mex is not compatible with Gurobi 5, so I would need to re-install Gurobi 4, I suppose.

[Johan Löfberg]

The error message does not make sense if you have a QP, as gurobi-mex supports that. Is it really a QP you have? Gurobi-mex is created for Gurobi 4 which doesn't support quadratic constraints, i.e, QCQPs. Maybe that is what you have?

[sebbesen]

You're probably right. I have a linear objective with quadratic inequality constraints, linear equality constraints and binary variables. How exactly would you classify this? Sorry for the confusion.

[Johan Löfberg]

A quadratically constrained linear program (term never used) which is a special case of quadratically constrained quadratic program (term used) which is a special case of a second-order cone program (most common term). Add mixed-integer in front since you have integrality constraints. The precise never used notation would be "binary quadratically constrained linear program" but we most often just say "mixed integer second order cone program"

Note that if you only have binary variables, you can solve the problem using a mixed-integer solver if necessary.

[sebbesen]

Thanks for the clarification! So, Gruobi 5 can (obviously) handle "mixed integer second order cone programming", but not Gurobi 4?

[Johan Löfberg]

Exactly

[sebbesen]

According to the Gurobi 5 documentation (e.g. >> help gurobi) there should be the possibility to define a MIP start vector (model.start). However, YALMIP does not seem to set this vector (yalmip2gurobi). Probably the problem is, as you already mentioned, that YALMIP introduces some internal variables. In fact, my original model has 3004 variables. Once entering yalmip2gurobi, the number of variables has grown to 4444, so it may be less obvious how to handle the starting values - or would it be fairly easy to hack YALMIP to set model.start?

[Johan Löfberg]

Indeed, simply add the following to the last line in yalmip2gurobi.m

if ~isempty(x0)

    model.start = x0;

end

You will probably not be able to use the solution though, since you only assign a sub-set of variables. Either flatten your model manually (I guess you are using abs operator or something like that, trivial to model manually), or, to test if it really helps to have the initial guess, first solve

solvesdp([constraints,myx == knownx],objective)

Now the internal values are assigned to some value, and you solve with this as an initial guess

solvesdp(constraints,objective,sdpsettings('usex0',1))

[Johan Löfberg]

Scratch my last two-step test. It will not work (new internal variables are defined)

[Mostafa Nick]

Hi Johan

Did you find any solution for MIP start of Gurobi in YALMIP?

Thank you so much in advance.

Best ragards

[Johan Löfberg]

Almost. Add

solver(i).supportsinitial = 1;

to line 116 in definesolvers.m (latest version), and it appears to work

x0 = randn(25,1) > 0;
y0 = randn(25,1);
A = randn(100,50);
b = A*[x0;y0]+rand(100,1)*10;

x = binvar(25,1);
y = sdpvar(25,1);

assign(x,x0);
assign(y,y0);
optimize([A*[x;y] <= b],sum(x)+sum(y),sdpsettings('solver','gurobi','usex0',1));

[jamieil]

Hi Johan,

not sure if this is the right place to ask, but since I couldn't find anything more up to date and since it seems related:

I'm trying to solve an MIQP in which constraints are modelled using the "implies" command. I'm using CPLEX and I'm trying (not successfully...) to assign an initial guess.
Above, you said that YALMIP using internal variables to model high-level functions is one cause - is this still up to date?

If so: Is there any chance to get it working by replacing "implies" by manual big M formulations? Or is CPLEX going to cause problems?
Thanks in advance!

[Johan Löfberg]

of course you can model it manually if you think you can derive stronger models

[jamieil]

Just to make sure: Initialization is not going to work when using "implies" for modeling?

[Johan Löfberg]

See what you mean. No, YALMIP will not be able to supply initial guesses on variables used for logic expressions