Skip to main content

Does adding known upper/lower bounds on the objective help MILP performance?

Answered
Phoenix Alpha
  • First Comment
  • First Question

Hello,

I have a question regarding MILP optimization performance.

I am minimizing an objective function that counts certain activation variables. From independent theoretical analysis, I know a tight lower bound and a tight upper bound for the optimal objective value.

When I run the MILP model without adding any constraint that incorporates these bounds, the solver works — but as the model size grows, the optimization becomes time‐ and memory‐intensive.

My question is:

If I  add constraints enforcing the known lower / upper bounds on the objective function variables, can that improve my model's performance and reduce optimization time?
For example, by adding a constraint such as:

obj >= LB

or :

obj <= UB

Would this help the solver prune the search tree earlier?

Any advice on whether providing such bounds is beneficial or not for branch-and-bound performance would be much appreciated.

Thank you

Related to

0

Comments

4 comments

Date Votes
  • Ryuta Tamura
    • Gurobi Staff

    Hi,

    Generally, it is said that setting upper or lower bounds on the objective function as constraints does not lead to performance improvement. This article and its linked content may be helpful:
    How do I pass an objective bound to Gurobi?

    Thanks,
    Ryuta

    1
  • Ryuta Tamura
    • Gurobi Staff

    Hi,

    I'll add a few comments. Adding a lower bound constraint to the minimization objective function can indeed potentially cause dual degeneracy. However, adding an upper bound constraint to the minimization problem may be effective, so it might be worth a try. Additionally, setting the Cutoff parameter instead of writing the upper bound as a constraint may also help.

    To determine whether model modifications help to solve the problem, it is necessary to test multiple seeds while considering performance variability. 

    The lower limit value may also be utilized in ways other than simply providing it as a constraint. For example, you can use that value to calculate a tighter MIPGAP within the callback function. This might allow you to write your own termination criteria.

    Thanks,
    Ryuta

    1
  • Phoenix Alpha
    Edited
    • First Comment
    • First Question

    Helllo,

    Ryuta Tamura Thank you so much for your response Ryuta, I will try with your suggestions and get back here. And I agree when I apply upper and lower bound at the same time as constraints that seems to be slowing down the optimization in my case. Now I am testing with just the upper bound as cutoff.

    I just have a question about lower bounds, just like cutoff can be used to apply upper bounds, do we have any similar parameter available to apply the lower bound as well? I mean other than the callback function thing. 

    0
  • Ryuta Tamura
    • Gurobi Staff

    Hi, 

    BestObjStop parameter may work. This parameter terminates optimization once a solution with the specified objective value or better is found.

    Thanks,
    Ryuta

    1

Please sign in to leave a comment.

Didn't find what you were looking for?

New post