Skip to main content

Improving Search Speed for solving MIQP using Gurobi

Answered

Comments

8 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • 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
  • 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

    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
  • 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
  • Micah Mungal
    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
  • 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

Please sign in to leave a comment.