Root relaxation objective value is different from the objective value from continuous model
AnsweredHello everyone,
I have a question regarding the root relaxation objective value.
The problem I am trying to solve is an integer program(IP). I modeled my problem as integer program (i.e. variable types are GRB.INTEGER) and let the stateofart solver Gurobi to solve it. I get the following root relaxation information from my log:
Root relaxation: objective 2.501961e+02, 3352 iterations, 0.12 seconds
In my own algorithm, I need to solve the continuous relaxation of (IP) at the first step. Therefore, I made the same model but changed the variable types to GRB.CONTINUOUS and let Gurobi to solve it. However, Gurobi cannot find the optimal solution for my continuous model within 1 hour, and the primal objective value is very far away from what I got at the root relaxation.
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 7.64857345e+00 1.07326045e+04 3.64e+01 3.85e+00 8.67e+01 123s
1 8.98710957e+00 1.21394933e+04 3.16e+01 2.85e+00 7.27e+01 223s
2 6.49839807e+03 1.26663297e+04 1.66e+01 2.49e+00 4.63e+01 325s
3 2.00139518e+03 1.33834110e+04 4.73e+00 2.74e06 9.85e+00 428s
4 1.76154917e+03 4.69790979e+03 4.28e+00 2.81e10 4.84e+00 529s
5 1.89292310e+03 1.11126958e+03 3.28e+00 2.87e10 2.95e+00 632s
6 2.06202435e+03 2.70380221e+03 2.73e+00 1.82e10 2.04e+00 733s
7 3.74002630e+03 8.63276088e+03 2.10e+00 1.26e09 1.82e+00 834s
8 8.35114242e+03 1.70416579e+04 1.32e+00 5.75e08 1.73e+00 935s
9 1.51000919e+04 2.33133433e+04 7.36e01 2.87e08 1.93e+00 1036s
10 3.09794008e+04 2.69140853e+04 3.24e01 5.43e07 4.37e+00 1138s
11 4.60406989e+04 3.17637908e+04 5.88e02 2.11e07 4.69e+00 1240s
12 3.57492040e+04 3.48549626e+04 2.17e03 4.97e07 2.87e01 1341s
13 3.51233448e+04 3.50944852e+04 3.82e04 5.86e07 8.97e03 1443s
Does anyone understand why this happens? My understanding is that the root relaxation solves the same model as my continuous model (general convex), so they should give me the same objective function value.
Thank you so much.

It sounds like you are relaxing your problem correctly. However, the root relaxation in Gurobi is more sophisticated than relaxing the integrality of a MIP. You can access this information by saving the presolved model or turn it off by turning off presolve.
For those just reading this article, you can follow along using the p0033.mps example model that comes packaged with Gurobi.
First, solve the original model:
model = gp.read('<installdir>/examples/data/p0033.mps')
model.optimize()The root relaxation for the original model is 2,839.
Next, you can solve the relaxed MIP using the model.relax() method:
model.reset()
model = model.relax()
model.optimize()The optimal solution of the relaxed MIP is 2,521. You can see that the root relaxation provides a tighter solution than the relaxed MIP.
To explore this difference further, it's interesting to do the following two solves:
First, turn off the presolve routine and solve as follows:
model.reset()
model.Params.PreSolve=0
model.optimize()Solving without presolve will give you a root relaxation of 2,521. You can see that this matches the relaxed MIP solution.
Next, you can solve the relaxed presolve model:
# Store the presolve model
model.reset()
presolve_model = model.presolve()
# Relax integrality, then solve
presolve_model = presolve_model.relax()
presolve_model.optimize()The final solve gives an optimal objective of 2,839. This matches our root relaxation from the original model.
1
Please sign in to leave a comment.
Comments
1 comment