Parameters for finding a single feasible solution of an MIP problem

Answered

Marcus Garvie

• July 24, 2023 14:47

Hi everyone,

I am solving pure binary linear programming problems in Gurobi v10.0 with no objective function. I understand the importance of tuning, which hasn't been very helpful for my problems (as my problems differ vastly in size and good parameters for one problem are not necessarily good parameters for another). I am interested in finding a single feasible solution as fast as possible. Are the following command line parameters appropriate/sensible?

MIPFocus = 1

SolutionLimit = 1

Is there any point using the 2nd parameter setting for the number of solutions when I've already set the 1st parameter setting? Another question I have is whether the equivalent CPLEX (v 12.10) parameter settings above are:

> set emphasis mip 1
> set mip limits solutions 1

Thank you,

Marcus Garvie.

Related to

• Solutions

0

• 

  Mario Ruthmair

  Gurobi Staff

  • July 25, 2023 13:55

  Hi Marcus,

  Your 2 parameter settings sound reasonable for quickly finding a feasible solution. SolutionLimit=1 actually changes some behavior in the solution process (apart from stopping after 1 solution has been found), so it makes sense to set it explicitly. You could also try the NoRel heuristic (parameter NoRelHeurTime), which is an optional heuristic that starts before the branch-and-bound phase. In a zero-objective model, it will stop as soon as it finds a feasible solution.

  Comparing those two parameters with similar ones in CPLEX is a bit difficult since the underlying solver behavior can be very different. Especially since MIPFocus and Emphasis are meta-parameters setting many other parameters under the hood.

  Best regards,
  Mario

  1
• 

  Marcus Garvie

  • July 25, 2023 15:46
  • Edited

  

  

  

  Thanks Mario.
  
  That is useful. I had thought that in Gurobi 'MIPFocus = 1' and 'SolutionLimit = 1' roughly corresponds to 'set emphasis mip 1' and 'set mip limits solutions 1' in CPLEX, respectively. But when I asked an expert in CPLEX (Paul Rubin) he told me that in CPLEX there is no point in settings the solutions limits to 1 if the mip emphasis was set to 1. So things are different in Gurobi and CPLEX (as you state).
  
  Can you suggest a sensible value for the NoRelHeurTime parameter that I might try?
  
  Thank you,

  Marcus.

  PS I just tried setting NoRelHeurTime = 600 (in addition to the other parameters) and I got a dramatic reduction in solve time for one of my problems (23.68 mins down to 4.84 mins).

  0
• 

  Mario Ruthmair

  Gurobi Staff

  • July 26, 2023 11:20

  A reasonable value for NoRelHeurTime is unfortunately not easy to guess, it depends heavily on your model. But this heuristic is usually quite good in finding a feasible solution. In the case you mentioned, NoRel did not use all the 10min you set, it stopped already after 4.84min since it found a feasible solution.
  Note that while NoRel runs, nothing else is happening, i.e., no branch-and-bound, no relaxation solve, etc.
  So, if it would not find a solution within 10min (NoRelHeurTime=600), then the usual branch-and-bound phase would start.

  0

Please sign in to leave a comment.