Skip to main content

multiple start vectors in matlab

Answered

Comments

5 comments

  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi Thomas,

    You can only add a single start solution to Gurobi when using the MATLAB API. Why do you need multiple start solutions? Shouldn't the best one be sufficient?

    If you absolutely need to supply multiple start vectors you should switch to another API, like Python.

    Cheers,
    Matthias

    0
  • Thomas Leveringhaus
    Gurobi-versary
    First Comment
    First Question

    Hi Matthias,

    thanks for your reply.

    I am using an sequential optimization approach, in which I solve an approximate MI-QCQP with Gurobi in each sequential step.
    So I use the integer values from the optimal solution of the sequential step before as starting value for the integer variables of the MI-QCQP of the current sequential step.
    For the continuous variables I don't submit a start value (but NaN instead) to force Gurobi to search for new values for them in the MI-QCQP of the current sequential step.
    Unfortunately it is not the case, that the integer values from the global optimal solution (params.MIPGap=0) of the sequential step before are globally optimal to the MI-QCQP of the current sequential step. And of course not all combinations of integer variables lead to an feasible solution. So Gurobi only has one start value from that it starts with solving and so it needs to repeat a lot of the search effort it already has done in the sequential step before to find integer feasible solutions.

    Tell me if I am wrong, but I expect gurobi to investigate the search tree at all submitted starts (if they can be submitted) and selects the best of them. I expect a high probability that one of the solutions found in the sequential step before is globally optimal to the MI-QCQP in the current step - but I don't know which one, and unfortunately it is not necessarily the one with the best objective value in the sequential step before.
    But even if non of the feasible solutions from the sequential step before delivers the global optimal solution to the MI-QCQP in the current step, I expect Gurobi to peform better if it already has investigated parts of the search tree, to have better heuristics and to find much more and better cuts etc.
    If there wouldn't be advantages, it wouldn't be possible to submit multiple starts in other APIs, would it?

    Will the Matlab API be extended in the future to include the ability to submit multiple starts?

    Can I circumvent the limitations by using gurobi_write() from MATLAB (https://www.gurobi.com/documentation/9.1/refman/matlab_grb_write.html) and adding multiple starts manually to one of the files?
    Or can I load multiple starts into the model-struct in MATLAB by using gurobi_read() of any file?

    Thanks

    Thomas

    0
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi Thomas,

    You cannot use gurobi_read() to read in start solutions - this is only for reading model files. You could try to export your model and then provide the solver with multiple solutions:

    gurobi_cl inputfile=start1.mst,sol1.sol,start2.mst model.mps

    This would produce an output like this:

    User MIP start 0 produced solution with objective 113.45 (0.00s)
    Loaded user MIP start 0 with objective 113.45
    User MIP start 1 did not produce a new incumbent solution
    User MIP start 2 did not produce a new incumbent solution

    Concerning how Gurobi deals with start solutions: They are mainly used to provide the solver with a primal solution right from the beginning, so there is a MIP gap immediately and nodes may be pruned earlier. Start solutions are also used to generate better solutions via improvement heuristics.

    Start solutions are processed before presolving and in the case of infeasible solution vectors, Gurobi checks them again in the presolved space. Then, the solver solves the root node (LP relaxation, cutting planes, heuristics, etc.) and proceeds with the branch-and-cut procedure. There aren't any other useful pieces of information that are used from the start solutions like the search tree you mentioned.

    There are no plans at the moment to extend the MATLAB API in this direction. The R and the MATLAB interfaces work differently than the other API in that they basically process all the information (settings, model, etc.) in one call. The other APIs allow for more fine-grained control of the solver and are recommended for more complex situations.

    I hope this answers your questions.

    Cheers,
    Matthias

    0
  • Thomas Leveringhaus
    Gurobi-versary
    First Comment
    First Question

    Hi Matthias,

     

    thanks for your detailed reply.

    It would really be nice, if you would make this feature available in die MATLAB API in some future days ...

     

    With your advices I was able to implement multiple starts but that was and is very unwieldy.

    I think there might be more smarter ways, but I didn't invest the time to optimize it. Maybe the approach helps someone else ...

    First, I need so save the model:

    gurobi_write(model, 'model.mps');

    Second, I manually need to create an attribute-file to hand over Var-Tags. I personally don't need the tags, but the JSON result file used later only contains variable values for tagged variables (...):

        fid = fopen('model.attr','wt');
    fprintf(fid, 'GRB_ATTR_FILE_VERSION 090002\n');
    fprintf(fid, 'SECTION VTAG\n');
    for v = 0:Anz.Varsneu-1
    fprintf(fid, ['C',num2str(v),' "Var',num2str(v+1),'"\n']);
    end
    fclose(fid);

    Third, I manually need to create a .prm-file for the parameters:

    fid = fopen('params.prm','wt');
    fprintf(fid, 'OutputFlag 1\n');
    fprintf(fid, 'PoolSolutions 2000000000\n');
    fprintf(fid, 'MIPGap 0\n');
    fprintf(fid, 'JSONSolDetail 1\n');
    fclose(fid);

    Fourth, I need to create an "inputfilestring" to hand over the changing number of starts and to create the according .mst-files:

    inputfilestring='';
    for s = 1:min(size(gurobierg.pool,2),8)
    model.start=NaN(Anz.Varsneu,1);
    model.start(model.vtype=='I' | model.vtype=='B')=gurobierg.pool(s).xn(model.vtype=='I' | model.vtype=='B'); % model.start must be a dense double vector
    gurobi_write(model, ['start',num2str(s),'.mst']);
    inputfilestring=[inputfilestring,'InputFile=start',num2str(s),'.mst '];
    end

    Fifth, I need to run Gurobi via the command-line interface from Matlab. As far as I could find out, the only way to write the solutionpool to file is as JSON-file, so I used that as ResultFile:

    system(['gurobi_cl ',inputfilestring,'InputFile=params.prm InputFile=model.attr ResultFile=solution.json model.mps']);

    Last, I need to load the JSON-data into Matlab:

    clear gurobierg
    gurobierg.json = jsondecode(fileread('solution.json'));
    for v = 1:Anz.Varsneu
    for s = 1:gurobierg.json.SolutionInfo.SolCount
    gurobierg.pool(s).xn(v,1)=str2double(gurobierg.json.Vars(v).Xn{s});
    end
    end
    gurobierg.x=gurobierg.pool(1).xn(:);
    gurobierg.objval=str2double(gurobierg.json.SolutionInfo.ObjVal);

    It works and as expected, Gurobi finds new incumbents from some starts of my model:

    User MIP start 0 produced solution with objective 0.749136 (60.63s) 
    Loaded user MIP start 0 with objective 0.749136
    User MIP start 1 did not produce a new incumbent solution
    User MIP start 2 produced solution with objective 0.744046 (215.01s)
    Loaded user MIP start 2 with objective 0.744046
    User MIP start 3 produced solution with objective 0.743473 (299.32s)
    Loaded user MIP start 3 with objective 0.743473
    User MIP start 4 did not produce a new incumbent solution
    User MIP start 5 did not produce a new incumbent solution
    User MIP start 6 produced solution with objective 0.733423 (438.98s)
    Loaded user MIP start 6 with objective 0.733423
    User MIP start 7 produced solution with objective 0.727408 (502.58s)
    Loaded user MIP start 7 with objective 0.727408
    Processed 8 MIP starts in 502.59 seconds

    Unfortunately gurobi_cl failed (without error warning) when handing over more than 8 .mst-files. Is that a known limit and is there a special reason for that?

    Obviuosly it takes a lot of time to complete the NaNs in each start, so I will have to weigh the effort against the benefit.

    Best regards

    Thomas

    0
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi Thomas,

    You are really putting a lot of effort into your MATLAB code! Please understand that we likely won't be extending the MATLAB API significantly in the near future. Its main use is "build a model, solve the model, inspect the solution". For virtually every other aspect that is more involved, we strongly recommend another API. You should get up and running very quickly with Python, judging by your proficiency with MATLAB.

    There is no limit on the number of start solutions you can pass to the solver.

    Kind regards,
    Matthias

    0

Please sign in to leave a comment.