Skip to main content

Improving Search Speed for solving MIQP using Gurobi

Answered
Micah Mungal
Gurobi-versary
First Comment
First Question

I am working on solving Unit Commitment problem. I am using Gurobi as the solver and Julia to create the model (MIQP model). However, I have been running the solver for a little over 24hours and notice the gap is decreasing very slowly. Currently, I am using the following Gurobi Parameters:

TuneCriterion = 2

CliqueCuts = 0

Cuts = 0

MIPFocus = 2

I have included a link to my log file and model in Julia. Any assistance in this matter is greatly appreciated. I should point out I could not save the entire log file from Julia's REPL, so I include the first couple of seconds of the log and most of the rest.

0

Comments

9 comments

Date Votes
  • Official comment
    Simranjit Kaur
    Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    Hi Micah,

    You could try experimenting with the NoRelHeurTime and MIPFocus parameter to shift the focus towards finding feasible points. Do you have an intuition of whether the lower bound bound or the feasible point should be improved. If it is the lower bound, then you should not turn of Cuts, as these are needed to move the lower bound. The PreQLinearize might also be worth testing.

    Could you provide an MPS file instead of the Julia code? This would make it way easier for the Community to help you. the Knowledge Base article How do I write an MPS model file from a third-party API? holds the required information.

    Best regards,
    Jaromił

    1
  • Micah Mungal
    Gurobi-versary
    First Comment
    First Question

    Hi Jaromil, thanks for the response. I believe that the lower bound should be improved. So I am trying the simulation over without turning off Cuts and MIPFocus = 3. I got the mps file, it can be found here: https://1drv.ms/u/s!AkuqGp7L6Ay2jPJ9d0r7-oQmGeWy_g?e=TScmCc

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    Hi Micah,

    The problem is quite large and has very high objective values. Do you really need to solve it to a MIPGap of 0.01%? I would guess that a MIPGap of 1% sounds more realistic. Of course, this depends on your application.

    Best regards,
    Jaromił

    1
  • Micah Mungal
    Gurobi-versary
    First Comment
    First Question

    Hi Jaromil, yes I understand that this problem is quite large, so I have no problem with a MIPGap of 1%. Since my previous comment, I have included

    PreQLinearize = 1,
    Method = 0,
    SimplexPricing = 2, 
    MIPFocus = 1.
     
    There were major changes at the beginning of the simulation, with a better integer solution being found quite early while the best bound took some time to increase. So I redid the simulation now using:
     
    PreQLinearize = 1,
    Cuts = 3,
    Method = 0,
    SimplexPricing = 2, 
    MIPFocus = 1.
     
    I now included aggressive cuts to improve the best bound. The simulation is running right now, but I am already seeing a slightly better incumbent and best bound value. However, one problem seems to be happening, the gap tends to rapidly decrease early in the simulation however when it drops to 10%, it take forever to decrease to 9%. Are there any other parameters I could try to get the gap to decrease much quicker. Thanks in advance.
     
    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Micah,

    It might be that your model suffers from a hard to find symmetry. Let's consider the equality constraint

    R0: C27216 + C27384 + C27552 + C27720 + C27888 + C28056 + C28224 + C28392
       + C28560 + C28728 + C28896 + C29064 + C29232 + C29400 + C29568 + C29736
       + C29904 + C30072 + C30240 + C30408 + C30576 + C30744 + C30912 + C31080
       + C31248 + C31416 + C31584 = 1016.34

    The constraints for the participating variables C27216 and C27384 are basically the same (they all have the same structure but with different binaries). This also applies to other pairs of variables in this constraint. Since the pairwise variables are interchangeable w.r.t. to their values and the corresponding constraints where they participate, the above equality constraint creates a very symmetrical structure which might be hard to detect. What you might try is to handle the pairwise variables as one variable or try to break the symmetry with additional ordering constraints, e.g., C27216 \(\geq\) C27384. The model is quite large so I hope that I did not miss something.

    Best regards,
    Jaromił

    1
  • Micah Mungal
    • Edited
    Gurobi-versary
    First Comment
    First Question

    Thanks for the feedback Jaromił. Based on the equality constraints mentioned above, I know this is associated with my load demand constraints where the sum of the power generated by each unit in the my electric grid must meet the load demand of 1016.34MW at the first hour of the week. There are 27 units in the system, hence the 27 different variables on the left hand side of the constraint. However, I know from the data associated with the units, that some of them have the same exact  specifications. For example, Unit 1 and 2 have the same specifications, Unit 3 and 4 have the same specification, Unit 5 to 8 are the same, Unit 9 to 14 are the same, Unit 15 to 17 are the same, Unit 18 to 20 are the same, Unit 21 is by itself, Unit 22 and 23 are the same and the Unit 24 to 27 are the same. I am not if this gives the impression that some of the variables are the same with different binaries?

    Also, I should point out this same model is solved very quickly using Gurobi for a smaller system with 10 Units for 24hours. However, I am now trying to now apply it to a much larger system with 27 Units and 168Hrs. So I know the system is quite large and I may have to settle with a MIPGap of about 10%.

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Micah,

    I am not if this gives the impression that some of the variables are the same with different binaries?

    Sorry for the confusion, I did not mean that C27216 = C27384 but rather that it would be possible to swap the values of C27216 and C27384 (and the corresponding binary variables) in the solution vector without making the solution infeasible and without worsening the solution value. Maybe, there is some trick to tighten the formulation hidden in there. In general, unit commitment problems are known to be very hard, even for small-medium sizes. I am not an expert on unit commitment problems. Maybe you can find something in the literature which might help here or someone from the Community has an advice.

    Best regards,
    Jaromił

    1
  • Micah Mungal
    Gurobi-versary
    First Comment
    First Question

    Thanks for all the help Jaromił, it is greatly appreciated. You were right about the symmetry issue, something I myself was unaware off. However, after doing some research last night, I came across this:

    Symmetry issues in mixed integer programming based Unit Commitment - ScienceDirect

     

    0

Post is closed for comments.

Didn't find what you were looking for?

New post