Solver time dependence on number of optimization variables and constraints

Answered

Shweta Meena

November 28, 2023 17:18

• 
• 

Hi all, 

MILP problem 1: N optimization variables, M constraints 

MILP problem 2: N+K optimization variables, M+L constraints, and the additional L (L>K) constraints are only dependent on the additional K variables, but the K variables values are already known and are captured in the optimization problem using K equality constraints which are subset of L. 

Can the Gurobi solver eliminate the redundant K variables and associated constraints in problem 2 and solve the problem in the same time as problem 1? 

 

0

• 

  Michel Soares

  November 29, 2023 11:22

  • 
  • 

  Hi,

  I assume the pre-solve time would be longer in problem 2.

  As for the solve time, depending on the order the pre-solve techniques are applied (meaning that it will not necessarily remove the K variables and L constraints first), you might get different models which will lead to different solve times. On not-too-large models or by using the strongest pre-solve parameter, it is more likely that you get the same model and hence similar solve times.

  Nonetheless, I suggest you give it a try. The most likely result is similar times for problem 1 and 2. If it is not the case, you can pre-process these variables and constraints to take them out, which should lead to similar or better results.

  1

Please sign in to leave a comment.