Skip to main content

Is best bound estimation always accurate as it is changing over time?

Ongoing

Comments

4 comments

  • Gurobot (AI-generated response)
    Gurobi Staff Gurobi Staff

    The best bound, also known as the lower bound for minimization problems (or upper bound for maximization problems), is an estimate of the optimal objective value that Gurobi computes during the branch-and-bound process of Mixed Integer Programming (MIP) solving. This bound is crucial because it helps in determining how close the current solution is to the optimal solution.

    From your logs, it's evident that the best bound is changing over time, which is a normal and expected behavior in the solving process. The solver continuously refines this bound as it explores more nodes in the search tree and solves more linear programming relaxations.

    However, it's important to understand that the best bound is an estimate and not always a precise indicator of the optimal solution's value. Several factors can affect its accuracy:

    1. Problem Complexity: In more complex problems, especially those with non-linearities or large solution spaces, it might be more challenging to estimate the best bound accurately.

    2. Solver Parameters: The settings and parameters you choose for the solver can impact how the best bound is calculated. For example, parameters like the integrality tolerance, the emphasis on proving optimality, and the quality of the MIP start solution can influence the best bound estimation.

    3. Time and Node Limits: If the solving process is stopped due to time limits or node limits before reaching optimality, as seen in your logs, the best bound may not be as close to the actual optimal solution as it could be if the solver had more time or resources to run.

    4. Cutting Planes and Heuristics: Gurobi uses various cutting planes and heuristics to improve the solving process. The effectiveness of these techniques can vary depending on the problem, impacting the best bound's accuracy.

    In your case, the final output shows a gap of approximately 24.33% between the best objective and the best bound, indicating that there is still a significant difference between the best known feasible solution and the estimated lower bound of the optimal solution. This gap can result from the solver not having enough time to fully explore the solution space or the complexity of the problem hindering a tighter bound estimation.

    In summary, while the best bound is a valuable tool in the optimization process, it's not always an exact indicator of the optimal solution's value, especially in more complex problems or when the solver's exploration is limited by time or other constraints.

    0
  • Sudheer Reddy
    Investigator
    First Comment

    How to conclude my best bound is not accurate.
    Is that possible by log values which I have shared

    0
  • Gurobot (AI-generated response)
    Gurobi Staff Gurobi Staff

    While you can't definitively say the best bound is inaccurate solely based on log values, a large optimality gap, slow convergence, and early termination of the solver are strong indicators that the best bound may not closely represent the actual optimal solution's value. It's important to interpret these logs in the context of your specific problem's characteristics and the solver's performance.

    0
  • Sudheer Reddy
    Investigator
    First Comment
    1. Regarding Improvement of Best Bound and MIPGap: In the initial logs before invoking the Gurobi callback, I noticed a trend where the best bound steadily improves over time, and simultaneously, the MIPGap reduces. However, when introducing additional binary variables to the same problem, I observed that the best bound fails to show improvement. Does adjusting the MIPFocus parameter offer any assistance in addressing this issue? Additionally, I'm curious about the potential reasons behind this contrasting behavior.

    2. Dealing with MIP Start and Objective Incumbent Solution: I encountered the following log message: "MIP start from previous solve did not produce a new incumbent solution." My goal is to load the MIP start from a previous solve while ensuring that the objective function is preserved. How can I overcome this constraint violation and successfully achieve my objective?



    0

Please sign in to leave a comment.