solving ILP models without an objective function
Answered
I am currently using Gurobi to solve a scheduling problem. I am
simply testing for schedulability, and am not looking to optimise anything at
this time. So, the first feasible solution encountered is returned back as the final solution. Does Gurobi still use Branch&Bound approach even to solve ILP models without an objective function ? Can you please direct me any documentation to see how Gurobi operates in such situations ? I am fairly new to Gurobi. Thanks.
-
Hi,
Assuming there is no objective function in your model, the Gurobi Optimizer would terminate with an optimal status as soon as it finds a feasible solution.
- If a feasible solution is found by one of Gurobi’s internal heuristic algorithms in the presolved stage, Gurobi Optimizer will not explore the search tree.
- If you set the NoRelHeurTime parameter to a non-default value, the no-relaxation heuristic will run before solving the root relaxation to find a feasible solution. If it succeeds, the Gurobi Optimizer would terminate without exploring the search tree.
- If no feasible solution is found in the presolved stage or by the no-relaxation heuristic, in case used, Gurobi will start exploring the search tree until a feasible solution is found either by branching or by a heuristic.
In case there is an objective function and you are interested to terminate the solver as soon as the first feasible solution is found, you can set the SolutionLimit termination criterion to 1 forcing the Gurobi Optimizer to stop as soon as the first feasible solution is found. Please note that setting this parameter to the value 1 initiates the usage of additional heuristic algorithms to find a feasible solution as quickly as possible. The quality of the feasible solution would be very likely poor using this approach.
Best regards,
Maliheh
0
Please sign in to leave a comment.
Comments
1 comment