Heuristic Parameter
AnsweredHello, I am a student who is writing a thesis.
I am looking for a MIP solution using a time limit of 60,000 seconds and a heuristic parameter of 5%. Does the 5% value only affect the time the heuristic runs (meaning 3,000 seconds run with the heuristic and the rest without the heuristic)? Or does it affect other things too in the heuristic processes?
Then may I know in detail what heuristic processes Gurobi uses to complete the MIP? I need these details for my thesis.
Thank You.
-
To address your question about the heuristic parameter and the detailed processes Gurobi uses in MIP solutions:
1. Effect of the
Heuristics
ParameterThe
Heuristics
parameter controls the fraction of time spent on heuristics during the solving process. You can think of the value as the desired fraction of total MIP runtime devoted to heuristics (so by default, we aim to spend 5% of runtime on heuristics).For instance:
- A value of
0.05
means the solver aims to spend roughly 5% of its decision-making efforts on heuristics relative to other processes. This could vary based on model complexity and progress.
2. Gurobi's Heuristic Processes in MIP
Gurobi employs several heuristic methods to find high-quality solutions early in the MIP solving process. These include:
a. Local Search Heuristics
- RINS (Relaxation Induced Neighborhood Search): Searches a subset of variables around the solution to the LP relaxation.
- Feasibility Pump: Alternates between finding solutions that are closer to feasibility or the integer space.
b. Probing
- Evaluates fixing variables and deduces implications to reduce the solution space.
c. Mutation Heuristics
- Attempts random or systematic perturbations in a feasible solution to discover better solutions.
d. Start Heuristics
- Uses the initial LP solution to guide the search for an integer feasible solution.
- Implements various rounding techniques for fractional values from the LP relaxation.
e. Guided Diving
- Explores promising branches early by prioritizing fractional variables based on their scores in the LP relaxation.
f. Solution Repair
- Repairs solutions that are near-feasible but violate constraints slightly, ensuring they fit the problem structure.
Also, I recommend the following video on heuristics: https://www.youtube.com/watch?v=SDT80rfNG_w. It is not specific to Gurobi but it contains relevant information.
- Bot
0 - A value of
-
Thank you for the answer, it really helped me in writing my thesis.
If I may, I would like to confirm further regarding the heuristic parameter value where I use a value of 5%. Is this value a certain standard in the heuristic processes? For example, if in a heuristic process a solution is obtained that is at least 5% better than the best solution at that time, will this be the new best solution, or another standard in the heuristic process? If it is a standard in a heuristic process, please state in what process and what the standard is.
Thank You.0 -
Hi Khadija,
The best solution at any point during the solve is called the incumbent solution. Any solution that is better than the incumbent becomes the new incumbent, even if it is only a tiny tiny tiny bit better. The heuristics parameter does not affect that. It only tells the solver how much time (approximately) to use with heuristics.
- Riley
0 -
Thank you for all the answers, very helpful:)
0
Please sign in to leave a comment.
Comments
4 comments