MIP gap
Answered
Hello All,
I have a multi-objective hierarchical optimization problem with about 450,000 variables (integer) and 355,000 constraints. After about 11 hours, the MIP gap for the first objective is 10%. Then, it takes about the same amount of time to decrease by 1 more % and then again twice that combined amount to decrease by an additional 1%. I am aware that the decrease in MIP gap is asymptotical which brings me to the following question.
Is there a way to know, a-priori, what kind of MIP gap corresponds to a good (enough) solution to a given optimization problem?
In other words, how do I know if an 8% MIP gap for example corresponds to a good solution to my problem if it takes forever to reach a lower percentage than that?
Thank you for your response.
-
Hi Alexia,
The parameters MIPGap and MIPGapAbs are indeed the performance metrics that can be used to quantify how good or bad a current solution is compared to the optimal solution.
A MIPGap of 1% can be good for one application and not good enough for another application. It is up to the user who knows the context of the application to interpret the MIPGap value.
Let us consider a minimization problem with the current incumbent solution of $10,000 and a MIPGap of 1%. This implies that the optimal cost will be greater than or equal to $9900. It is then up to user to decide if it makes sense to accept a near-optimal solution which costs an extra $100 at most or not.
Best regards,
Maliheh
0
Please sign in to leave a comment.
Comments
1 comment