Can constraints speed up solving a model? (Or would there be a better way to introduce information?)

Answered

Jack Keefer

• September 18, 2023 22:07

I am currently working a project in which I use Gurobi many times (as the inner most loop of a few nested loops). Each time, I construct a model in which I determine if an individual will participate in a program and if they participate, which group they will participate in. The two decisions are interconnected as they will participate if they receive positive net value from participation, but, their participation value depends on what group they are in and what other individuals are in that group. The problem Gurobi solves each time is a MILP program, where all the choice variables are binary, but interact in non-linear ways. I typically have about 40 individuals, each with a participation variable and ~5 possible group variables (including one that is a "participate solo" variable). It currently runs very slowly once the number of individuals goes above around 30. 

However, I can analytically (and by coding up a set of "rules", automatically) determine that some individuals will participate and others won't. I can choose to not pass the individuals that won't participate into Gurobi (as they won't interact with any other individual as a result). However, I still need to pass the participating schools to Gurobi as I need to find their grouping choice and its effect on other individuals' decisions. 

 

I could use constraints to set their participation variable equal to 1 if I know they will participate. However, is this the best strategy to introduce information I know to Gurobi? Will adding additional constraints speed up solving (as it will eliminate a number of potential solutions), or will it slow it down (as there are now more constraints)? 

Does anyone have any tips on how to incorporate information I have or other means of speeding up the process?

 

 

0

• 

  Jaromił Najman

  Gurobi Staff

  • September 19, 2023 08:12
  • Edited

  Hi Jack,

  If you can automatically determine additional model knowledge which would result in fixing some binary variables (or tightening the formulation), you should always definitely add this information to your model. The reason is that deducing such information from a solver's perspective may be very hard or even unachievable and the solver often has to do a lot of work in order to get the knowledge during a solution process.

  Using additional model knowledge and adding this as constraints usually helps the solution process as long as the constraints are not just linear combinations of all other constraints or almost parallel which may lead to numerical issues instead of actually helping the solution process.

  [...] or other means of speeding up the process?

  You could try finding specific solver parameters which might speed up the solution process. For this, please have a look at the Most important parameters for MIPs.

  Best regards, 
  Jaromił

  0

Please sign in to leave a comment.