MIP - Time limit - Extracting best feasible solution in given time limit

Answered

Kalyana Namburi

January 31, 2024 07:29

• 
• 
• 

Hi Gurus,

I have a MIP problem that will take a long time to solve to optimality. As I only need a "good" feasible solution. What are the parameters to set and how to extract the best feasible solution are my challenges.

I have tried the usual suspects with MIPFocus 1. The Solution Limit is of no use as solver terminated early with some trivial but feasible solution. I want to run the 600 second timelimit and find the best "feasible" solution. Since the solution pool might have both feasible and non-feasible, how do we extract out best feasible solution from solution pool?

m.setParam('TimeLimit', 600) # Set the time limit to 600 seconds

m.setParam('Heuristics', 0.8) # Focus most of the time on feasibility and feasible solutions

m.setParam('MIPFocus', 1) # Prioritize quality feasible solution over optimality

m.setParam('ImproveStart', 1) # Enable solution improvement

m.setParam('PoolSolutions', 10) # Set the maximum number of solutions in the solution pool

# m.setParam('SolutionLimit',5) # Limits the number of feasible MIP solutions. m.setParam('NoRelHeurTime', 300) # Limits the amount of time (in seconds) spent in the NoRel heuristic

m.setParam('MinRelNodes', 500) # Adjust the value based on experimentation

m.setParam('PumpPasses', 10) # Adjust the value based on experimentation

m.setParam('ZeroObjNodes', 500) # Adjust the value based on experimentation

Related to

• Solution Pools

0

• 

  Marika Karbstein

  • Gurobi Staff

  January 31, 2024 08:02

  Hi Kalyana,

  If you are interested in good solutions, experimenting with the parameters NoRelHeurTime and Heuristics is a good idea. 

  The parameters MinRelNodes, PumpPasses, ZeroObjNodes could help if it is hard to find a first feasible solution. But if I understand correctly, it is no problem to find a first (probably trivial) solution. In this case, you should keep these parameters at their default values.

  Since the solution pool might have both feasible and non-feasible, how do we extract out best feasible solution from solution pool?

  I am not sure what you mean by this. Why do you think the solution pool contains infeasible solutions?
  The best solution (with the best objective value) found so far is always the first solution in the solution pool.
  If you are only interested in the best solution, you do not need to handle a solution pool. The best solution can be accessed via the model attribute ObjVal to get the objective value and via the variable attribute X to get the solution value for the variables. You can also write the best solution into a file using the parameter ResultFile.

  If you have a commercial Gurobi license, you can create a support request via our Help Center and share the MPS model file with us. We can then help to find the best parameter setting for this model.

  Best regards,
  Marika

  0
• 

  Kalyana Namburi

  January 31, 2024 09:05

  • 
  • 
  • 

  Hi Marika,

  Thanks a lot for the insights. This is great help !

  I was trying to figure out if further calculations are needed to "check" for feasibility on candidates from the solution pool. Can you please advise if Gurobi stores only feasible solutions as part of the solution pool. 

  Regards

  Kalyan

  0
• 

  Marika Karbstein

  • Gurobi Staff

  January 31, 2024 09:37

  Hi Kalyana,

  Yes, the solutions in the solution pool are usually feasible.
  However, if the model has numerical issues, it could be that a solution violates some tolerances. In this case, you will find a warning in the Gurobi log file, for example

  Warning: max bound violation (1.6729e-06) exceeds tolerance
  Best objective 3.320495458346e+10, best bound 3.318538760989e+10, gap 0.0589%

  The solution quality can be checked for example in Python using Model.printQuality() 
  It is also possible to check the solution quality attributes MaxVio or BoundVio for the maximum constraint or bound violation, see Quality Attributes for additional attributes.

  The Python example poolsearch.py shows how the solutions in the solution pool can be accessed.
  This example is also available for the other APIs, see Gurobi Optimizer Example Tour.

  Best regards,
  Marika

   

  0

Please sign in to leave a comment.