Which solution is reported when I set the time limit for my Model.
AnsweredHello,
I am running Gurobi to solve a Lagrangian Decomposition algorithm in which I divide the problem into subproblems 1 and 2 named as m1 and m2 in Gurobi. Both are minimization problems. Summation of Optimal solution to these subproblems provides me best lower bound. However, these problems being large in size, I set a time limit (500 sec) for each of these subproblems.
I retrieve the solutions using Z1 = m1.ObjVal and Z2 = m2.ObjVal. The lower bound is set to Z1+Z2. I want to know if the lower bound is valid to the overall problem because I am not solving the subproblems to optimality.
Suppose optimal solution to the overall minimization problem is 100. Would limiting the time provide me solution greater than 100 or lower than 100? I would like to retrieve the solution that is <100 because that keeps my bounds valid. What are the methods to do this?
I have the same question for setting MIP GAP?
Amogh
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
When you have a minimization problem with optimal value 100, then at any point in time the incumbent objective value will be
primalbound >= 100
while the objective bound will be
dualbound <= 100
When both primal and dual bound become exactly 100, then the optimality of the incumbent solution has been proven and the optimization stops with an "Optimal" status.
So, in your case it could be, for example, that after aborting due to the time limit you have the following bounds in the two subproblems:
primalbound1 = 53
dualbound1 = 44
primalbound2 = 72
dualbound2 = 48That means, you have found a feasible solution for the full problem with value 53 + 72 = 125, and you know that there is no solution that is better (i.e., has smaller value) than 44 + 48 = 92.
In this example, the MIP gap for subproblem 1 would be (53-44)/53 = 9/53 = 0.17, and the MIP gap for subproblem 2 would be (72-48)/72 = 24/72 = 0.33. For the full problem, you would have a MIP gap of (125-92)/125 = 0.264, but this you have to calculate yourself, because you cannot calculate it out of the two MIP gaps provided by Gurobi for the two subproblems.
Regards,
Tobias
0 -
-
You are absolutely right Tobias and this is exactly what I do.
I guess I wasn't clear enough.
I have set up the time limit parameter to 500 seconds for models m1 and m2.
So my question is does command "m1.ObjVal" gives me primalbound1 or dualbound1? If it does provide primal bound then I am using incorrect bounds. Is there another command to that gives me best dual bound found so far.
Amogh
0 -
-
Thank you.
0 -
Post is closed for comments.
Comments
5 comments