Running time is longer when the problem size is decreased

Answered

Miranda

August 26, 2022 02:42

• 
• 
• 

Hello, 

I have a question regarding the Gurobi solver. I solved two mixed integer programmings (named MIP1, and MIP2 respectively) which are in the same structure/formulation (they are all set-packing problems and the size of each set is at most 3). The number of decision variables of MIP2 (230,000) is much less than that of MIP1 (330,000). However, the time that Gurobi takes to find an optimal solution to MIP2 is longer than the time to solve MIP1. Therefore, my question is, if two MIPs are in the same formulation but one has less decision variables, is it always the case that Gurobi would find an optimal solution to the small problem more quickly? If not, could I ask the reason behind? (If the running time is not determined by the number of decision variables, then what other factors do I need to consider) 

Thank you so much for your time and help. 

Best.

0

• 

  Jaromił Najman

  • Gurobi Staff

  August 26, 2022 14:43

  Hi Miranda,

  Unfortunately, one can usually not state a priori that model A will solve faster than model B. This also applies even if both models have the same structure/formulation. There can be many different reasons for this behavior. One possibility is that for model A Gurobi finds a feasible solution which leads to a certain path in the B&B tree which makes it converge fast. For a smaller model B of the same structure, Gurobi finds a feasible solution with different properties, which leads to the exploration of a different path in the B&B tree taking more time in the end.

  You could try running your models with multiple different Seed parameter values to see whether your models are prone to performance variability, i.e., that your models are prone to already small changes in the solution path. If you find out that different seeds have quite an effect on the solution process, you could try running Gurobi's tuning tool to find parameters which might not only speed up the solution process but also improve performance stability w.r.t. to different seeds.

  Best regards, 
  Jaromił

  0

Please sign in to leave a comment.