Skip to main content

Heuristic Parameter

Answered

Comments

4 comments

  • Bot Marley (with AI contributions)
    Detective
    Thought Leader

    To address your question about the heuristic parameter and the detailed processes Gurobi uses in MIP solutions:

    1. Effect of the Heuristics Parameter

    The 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
  • Khadija Sakinah Kusumadila
    First Comment
    First Question

    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
  • Riley Clement
    Gurobi Staff Gurobi Staff

    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
  • Khadija Sakinah Kusumadila
    First Comment
    First Question

    Thank you for all the answers, very helpful:)

    0

Please sign in to leave a comment.