Stochastic programming with YALMIP and warm starting solvers

[Mahdi Kefayati]

Hi!
I have been searching around to see if anyone has done stochastic programming (say two stage linear or MILP) with YALMIP and did not find any.
I have already implemented my problem (2 stage with arbitrary number of second stage scenarios) in YALMIP in a deterministic equivalent form. The problem, however, is that it is not very scalable.
The standard way to deal with this is to do an L-shaped Method/Benders Decomposition/... yet, the way I understand it, is that I would need to be able to warm start the deterministic solver. I know Some solvers like CPLEX support it, yet, I am not sure if YALMIP supports warm start. Any comments?

[Johan Löfberg]

No, warm-starting from YALMIP is not possible in general. Not the right tool for the job.

[Mahdi Kefayati]

OK!
Regarding being the right tool, honestly, I have not seen many, if any, tool in MATLAB for stochastic programming.

Is it really hard to add such a functionality YALMIP? What are the challenges?

[Johan Löfberg]

Well, you are talking about two different things now. Warm-starting is one thing, and the problem here is that good warm-starts typically requires more than a good previous solution (if an interior-point solver is used, you need good duals, and some recovery from the fact that something has changed)

Stochastic programming is something which might be added in the future when I get sufficiently interested in the topic. As you maybe know, there is already support for robust programming, which is a close cousin to stochastic programming. The challenge is to make it general enough to be of general interest, while making it scale to be of practical interest.

[Mahdi Gh]

Hi Johan, 

Does the current version of Yalmip support warm-starting for MILP? If the answer is yes, would you please share with me a working example or the corresponding commands? 

[Johan Löfberg]

Yes, some MILP solver support initial guesses and YALMIP then supports that through assign - usex0 logic as explained in final example here

https://yalmip.github.io/command/assign/

[Mahdi Gh]

Would you please advise me for which MILP solvers warm starting is supported through the Yalmip interface. I specially would like to use Gurobi:  

sdpsettings('solver','gurobi','usex0',1)

If Gurobi is not supported, how about Mosek?

[Mahdi Gh]

Also, for the current version of Yalmip should I manually add the below command to definesolvers.m file? 

solver(i).supportsinitial = 1;

 If the answer is yes, please let me know at which line of the file?

[Johan Löfberg]

No, that would not make any difference. This flag is used to announce internally in YALMIP that the specific solver has support for initials, but simply changing the value of the flag without actually adding code for actually communicating the initial values won't help of course. As a user, you use assign and the usex0 options if the solver supports initials

[Johan Löfberg]

gurobi supports, mosek doesn't (through yalmip)

[Mahdi Gh]

Can I use warm starting with Gurobi through the Yalmip interface?

[Mahdi Gh]

Hi Johan, 

I have used     assign(x,x0)     and      sdpsettings('solver','gurobi','usex0',1)  to warm start

an MILP. Here, x0 is a feasible solution for the MILP. However, warm starting didn't reduce the computation time. 

1- Is it likely that Yalmip is changing my MILP model internally and produces a new internal problem that doesn't have an initial warm start? 

2- How can I realize whether Yalmip is using the initial guess x0. 

3- How can I force MILP to not change my model internally, so that warm starting takes effect.

4- Does changing the solver from Gurobi to Cplex or Mosek may make the warm starting work? 

[Johan Löfberg]

if you are using high-level milp-representable operators, then there will be integer variables that you haven't assigned (nonconvex abs, implies, sort etc etc)

you can see if initials have been assigned and used by comparing the display for the first couple of nodes. if assigned you should recognize a different upper bound

however, having an initial guess, even the optimal one, does not necessarily improve performance, if the main challenge is proving lower bound. there are many problems where it is trivial to find the globally optimal solution bit it takes ages to prove it is optimal