Skip to main content

Method to speed up solving many small MIPs

Answered
Ryan Killea
First Comment
First Question

For my use case inside a larger algorithm I have to solve many small, similar, MIPs. Each MIP has < 100 variables and < 200 constraints typically. These numbers may grow as I make improvements, but for now these problems are what I care about.

I would like to maximize the throughput Gurobi has for these problems. Currently each solve+creation takes roughly 0.004-0.005 seconds, and I am wondering if that is a kind of limit (Python API, would using the C++ API be noticeably superior here?). I have set BestBdStop and BestObjStop for these programs and I expect typical behavior to be the optimization is stopped by BestBdStop.

When I solve LPs I know about using the VBasis/CBasis loading to warm start, but for MIPs I am really looking to improve solution time by any method. If I solve the relaxation first (I also use reduced costs in my procedure) can Gurobi take advantage of that at all? Similarly, if I expect the optimization to terminate by being stopped, should I instead phrase it as a constraint, and set the objective to 0, then warm start? I would have to rewrite a large chunk of my code to do this, but is there a significant improvement possible if I were to use the Multi-Scenario feature, or does that not kick in for models these small? Is it a lost cause to try to get more performance out of these extremely small problems?

Lastly, what is the best practice around copying vs modifying a model? If I need to re-specify all linear expression coefficient terms for a subset of my constraints (same variables) as well as about half of my variable upper and lower bounds each optimization, is it better to create a base model, copy it, then add, or create a base model, copy it, then modify, or create a new model each time? Assume previous solution information is not helpful for this case.

Related to

0

Comments

3 comments

Date Votes
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Currently each solve+creation takes roughly 0.004-0.005 seconds, and I am wondering if that is a kind of limit (Python API, would using the C++ API be noticeably superior here?)

    Which of the two takes more time, solving or creating the models? If it is creating and you need every little millisecond of performance then I would go with the C++ API. If it is model solution, then you should try tuning your model(s) with parameters. You could use Gurobi's automatic parameter tuning tool (an older video can be found here). This way, you can let Gurobi find parameters to decrease running time for your base model(s) which then hopefully would apply to the modified models as well. Given the super small runtimes of your models, I would try turning off reductions and cuts to save every millisecond possible, Presolve=0, Cuts=0, Method=?.

    I have set BestBdStop and BestObjStop for these programs and I expect typical behavior to be the optimization is stopped by BestBdStop.

    That's very good.

    If I solve the relaxation first (I also use reduced costs in my procedure) can Gurobi take advantage of that at all?

    I don't see how solving the relaxation a priori might help for a MIP.

    Similarly, if I expect the optimization to terminate by being stopped, should I instead phrase it as a constraint, and set the objective to 0, then warm start?

    You are already using the BestBdStop and BestObjStop parameters. If you have any other termination criteria for your models, you might want to use those via a callback and call terminate from within a callback.

    I would have to rewrite a large chunk of my code to do this, but is there a significant improvement possible if I were to use the Multi-Scenario feature, or does that not kick in for models these small?

    The multi-scenario feature might have a positive performance impact. Unfortunately, this is not something that can be said without experimenting with it. For now, I would try to stick to your "classical" approach before rewriting large parts of your code to use the Multi-Scenario feature.

    Is it a lost cause to try to get more performance out of these extremely small problems?

    It depends on how crucial the performance benefit is. If you can squeeze out tiny bits of milliseconds for each model solved and you solve enough models then it is definitely worth a try. Of course, there might be a point where no improvement can be made but it is at least worth a try.

    Lastly, what is the best practice around copying vs modifying a model? If I need to re-specify all linear expression coefficient terms for a subset of my constraints (same variables) as well as about half of my variable upper and lower bounds each optimization, is it better to create a base model, copy it, then add, or create a base model, copy it, then modify, or create a new model each time? Assume previous solution information is not helpful for this case.

    If you want to save as much time as possible, then you should definitely modify one model instead of copying it. If you know which coefficients and constraints are changed in each iteration of your algorithm, you could pre-define these particular variables and constraints and use the GRBModel::chgCoeffs() method to change all at once. If you really want to squeeze out every last millisecond, then you should consider switching to C, where you could save some precious time by avoiding working with Constraint and Variable objects but with integer indices only.

    If you know that the previous solution information is not useful, you might want to experiment with the reset method to avoid having Gurobi evaluate a MIP start from previous solution.

    Best regards, 
    Jaromił

    1
  • Ryan Killea
    First Comment
    First Question

    Thank you Jaromił,

    Your answer is very helpful.

    I had tried Gurobi's automated parameter tool, but I think that I used it incorrectly (on single problems) so the parameters are not consistent (outside of obvious ones like turning off the logging output). It did not yield a gain as a result, but I will try again using the reference you've provided. Close to half the time is spent setting up the models so I'll try porting that to C++ if it will make a noticeable difference. Unfortunately I don't have more interesting ways to terminate so I don't think a callback will help me.

    The idea behind using a relaxation first would be solve the following problem (which has a high probability of being infeasible):
    Max 0 s.t.
    objective >= lower bound
    constraints
    Which might be easier to solve or otherwise hint that feasibility should be a top priority. Then if the MIP does solve, I have a feasible point to warm start the optimization from. It was just an idea I had.

    I expect to solve hundreds of thousands of these models in a run, so yes, any small performance benefit will have a massive impact.

    Thank you for the advice regarding the precise methods in C and C++ that are most optimal (and not to copy models) to set up the models quickly!

    I have been experimenting with reset, but I think porting to C++ (and then C if necessary) is the logical next step given your answers. The constraints which change the most frequently will be variable bounds followed by a small subset of coefficients.

    Thanks,

    Ryan

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Ryan,

    I had tried Gurobi's automated parameter tool, but I think that I used it incorrectly (on single problems) so the parameters are not consistent (outside of obvious ones like turning off the logging output). It did not yield a gain as a result, but I will try again using the reference you've provided.

    Given the extremely short runtimes, it is possible that the tuning tool cannot find anything consistently. You should try experimenting with the Most important parameters for MIPs. In particular, try turning off most of them.

    Close to half the time is spent setting up the models so I'll try porting that to C++ if it will make a noticeable difference.

    How exactly do you modify your model(s)? Before moving to C++, you might want to profile your Python code via timings

    import time
    start = time.time()
    # your code
end = time.time()
print(end-start)

    Usually, changing a few variable bounds and/or coefficients should be faster than solving the model.

    The idea behind using a relaxation first would be solve the following problem (which has a high probability of being infeasible):
    Max 0 s.t.
    objective >= lower bound
    constraints
    Which might be easier to solve or otherwise hint that feasibility should be a top priority. Then if the MIP does solve, I have a feasible point to warm start the optimization from. It was just an idea I had.

    This might work and if it's not too hard to implement, you might want to try it out.

    The constraints which change the most frequently will be variable bounds followed by a small subset of coefficients.

    You can change variable bounds via accessing the attributes. In Python, this would be

    x.lb = 5 # change lower bound of variable x
    x.ub = 6 # change upper bound of variable x
    x.obj = 7 # change objective coefficient of variable x

    In C++, you would use the GRBModel::set() method.

    Best regards, 
    Jaromił

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post