Why is Gurobi returning MIP solution with gap of 0 which is not close to the actual optimal solution?
OngoingUsing the below code and the following two .csv files, Gurobi returns an optimal solution of 62.42 when the parameter SET_SOME_VARS is set to 0, but returns a much better solution (of 12.32) when it is set to 1. But setting it to 1 is just forcing one feasible solution for the problem, so why is the version without these constraints finding a much worse "optimal" solution? The MIP solution ends with a gap of 0 in both cases.
Thanks in advance for any insights on this!
(Census_Population_1970.csv can be obtained via this google sheet):
https://docs.google.com/spreadsheets/d/1yS7FWRrknAEUnQzDXu1Fv0eiY2UplY_ElQleXcyMqOQ/edit?usp=sharing
(moo93.csv can be obtained via this google sheet):
https://docs.google.com/spreadsheets/d/1NkuxVslk9PhpFv0eujiNvnOaBK7nWf6ekexn3dkcsjk/edit?usp=sharing
library(readxl)
library(writexl)
library(Matrix)
library('gurobi')
setwd("C:/Users/Steven Shechter/Dropbox/R/Gurobi/Apportionment_Gurobi")
SET_SOME_VARS < 0 # setting to 1 forces some of the decision variables to take on certain preset value
# setting to 0 lets Gurobi optimize these and the other variables
total_reps < 435
num_states < 50
obj_weight_pairwise < 94
obj_weight_range < 100obj_weight_pairwise
data < read.csv("Census_Population_1970.csv")
total_pop < sum(data$Population)
data$quota < data$Population/total_pop*total_reps # the # of seats the state should get under continuous reps by
###########################
# SET UP DECISION VARIABLES
###########################
num_x_vars < num_states
num_v_vars < (num_states1)*num_states/2
num_y_vars < 1
num_vars < num_x_vars + num_v_vars + num_y_vars
model < list()
#setting up the x vars
for (i in 1:num_x_vars)
{
model$vtype[i] = 'I'
model$varnames[i] = paste0('X', i)
model$obj[i] = 0
model$lb[i] = 1
}
#setting up the v vars
for (i in 1:num_v_vars)
{
var_index < num_x_vars + i
model$vtype[var_index] = 'C'
model$varnames[var_index] = paste0('V', i)
model$obj[var_index] = obj_weight_pairwise #the weight given to the v vars
model$lb[var_index] = 0
}
# setting up the y vars
for (i in 1:num_y_vars)
{
var_index < num_x_vars + num_v_vars + i
model$vtype[var_index] = 'C'
model$varnames[var_index] = paste0('Y', i)
model$obj[var_index] = obj_weight_range #the weight given to the y var
model$lb[var_index] = 0
}
###########################
# SET UP CONSTRAINTS
###########################
# Constraint 1: sum of x vars = 435
model$A < matrix(c(rep(1, num_x_vars), rep(0, num_v_vars), rep(0, num_y_vars)), nrow = 1, byrow = FALSE) # constraints of type labeled constraint 1 above (which is just 1 constraint)
model$sense < '='
model$rhs < total_reps
#TESTING: activating the following code chunk returns a feasible solution with a better objective value (12.32),
# compared to the objective value of 62.42 the optimization returns when it is deactivated
if(SET_SOME_VARS) {
# Constraints to fix x vars at certain values given in the following .csv file (obtained by a weighting of 93 and 7 instead of 94 and 6)
moo93 < read.csv("moo93.csv")
B < spMatrix(num_x_vars, num_vars,
i = (1:num_x_vars),
j = (1:num_x_vars),
x = rep(1, num_x_vars))
model$A < rbind(model$A,B)
model$sense < c(model$sense, rep('=', num_x_vars))
model$rhs < c(model$rhs, moo93$MOO93)
}
# Constraints to set up the v and y variables to take on the intended objective values
v_index < 1
qc_index < 1
cumulative_quadcon < list()
temp_list < list()
for (i in 1:(num_states1))
{
for (j in (i+1):num_states)
{
temp_list$Qc < spMatrix(num_vars, num_vars, c(i, j), c(i, j), c((data$quota[i])^(2), (data$quota[j])^(2)))
temp_list$q < sparseVector(c((data$quota[i])^(2), (data$quota[j])^(2), 1), c(i,j,num_x_vars+v_index), num_vars)
temp_list$rhs < 0
cumulative_quadcon[[qc_index]] < temp_list
qc_index < qc_index + 1
temp_list$Qc < spMatrix(num_vars, num_vars, num_vars, i, 1/data$quota[i])
temp_list$q < sparseVector(1/data$quota[j], j, num_vars)
temp_list$rhs < 0
cumulative_quadcon[[qc_index]] < temp_list
qc_index < qc_index + 1
temp_list$Qc < spMatrix(num_vars, num_vars, c(i, j), c(i, j), c((data$quota[i])^(2), (data$quota[j])^(2)))
temp_list$q < sparseVector(c((data$quota[i])^(2), (data$quota[j])^(2), 1), c(i,j,num_x_vars+v_index), num_vars)
temp_list$rhs < 0
cumulative_quadcon[[qc_index]] < temp_list
qc_index < qc_index + 1
temp_list$Qc < spMatrix(num_vars, num_vars, num_vars, j, 1/data$quota[j])
temp_list$q < sparseVector(1/data$quota[i], i, num_vars)
temp_list$rhs < 0
cumulative_quadcon[[qc_index]] < temp_list
qc_index < qc_index + 1
v_index < v_index + 1
}
}
model$quadcon < cumulative_quadcon
model$modelsense < 'min'
params<list()
params$NonConvex < 2
# solve model
result < gurobi(model, params)
if (result$status == 'OPTIMAL') {
data$reps < result$x[1:num_states]
} else {
cat('Optimization finished with status',result$status)
}

Hi Steven,
Could you use the gurobi_write() function to write 2 LP files (one with SET_SOME_VARS=0 and the other with =1) and upload those? This would make helping you easier.
Best regards,
Jaromił0 
Thank you, Jaromil. I don't see how to upload a file, but here are links to google docs with the .lp outputs. These are long files, but I ran a "compare" of these in Word and confirmed that the only differences between the files are that the first one explicitly forces the integer variables to take on specific preset values (shown in the "differences" doc.
when setting SET_SOME_VARS < 1:
https://docs.google.com/document/d/1mqcMFi2QFqCijP7YY6mSOSGvVhA6hzBH3WZ3U3AmTlw/edit?usp=sharing
when setting SET_SOME_VARS < 0:
https://docs.google.com/document/d/1hjtd7vec5Tka0uu10cCcPphxpy8Z2S2ZLBIxPk5pI/edit?usp=sharing
The differences between these two files results in:
https://docs.google.com/document/d/1hjtd7vec5Tka0uu10cCcPphxpy8Z2S2ZLBIxPk5pI/edit
0 
sorry, the differences link should instead be:
https://docs.google.com/document/d/1NePZgZ0PcSFUG8Mwh0byCEQAs0KNJIKLEdA1iR9g5GA/edit?usp=sharing
0 
I observed a few cases of incorrect solutions with Gurobi 9.1.09.1.2, similar to what you described. However, I couldn't replicate this behavior with Gurobi 9.5.0. Which version of Gurobi are you using? Could you please post the log output printed by Gurobi when \( \texttt{SET_SOME_VARS} \) equals \( 0 \)?
0 
Thank you, Eli! That did the trick. I was using version 9.1.2. The problem no longer appears after I updated to version 9.5.0. Was the problem in 9.1.2 related to my model's use of nonconvex quadratic constraints?
thanks again!
0 
That's great to hear! Yes, your intuition is correct  the problem in Gurobi 9.1.2 was related to the nonconvex quadratic constraints.
0 
Hi Eli,
I'm actually running into similar problems again as described above, even for the 9.5.0 version of Gurobi.
Same situation, where the "optimal" solution returned by Gurobi is worse (by two orders of magnitude) than another feasible solution obtained after fixing several decision variables. I set MIPGap to 0 in both cases (and the log files show the problems terminating with gap 0.0000%). These are also again occurring in a nonconvex quadratically constrained problem.
The log files are here:
Solution without prefixing decision vars:
https://docs.google.com/document/d/1kvomcFwnFLMfersRXSxGOytictNTzAi6yP_KobUhFk/edit?usp=sharing
Objective value (for a minimization problem): 85.7
Solution with prefixing several decision vars:
https://docs.google.com/document/d/1s0y34J8LFw9OtuL2oPOXKsCFbUX1NAw9uG2Dx5euOc/edit?usp=sharing
Objective value: 0.408
thanks in advance for any insights you may have on this!
best,
Steven
0 
Could you post a link to MPS model files for the two models that produce these different results? You can create these model files using the gurobi_write() function, as you did before. Thanks!
0 
Sure.
The MPS file for the version that fixes the 48 integer variables at predetermined values is here:
https://drive.google.com/file/d/1DJKiieKbyhwBoda0LBkumJAXZiEQC5su/view?usp=sharing
and the MPS file that does not fix the 48 integer variables is here:
https://drive.google.com/file/d/1sAeDBgzLawVRphs267yba7pj4izQ3H/view?usp=sharing
thanks again for having a look!
Steven
0 
Hi Eli,
I just wanted to follow up on this and see if you were able to find out what the issue might be?
Thank you!
Steven
0 
Sorry, Steven. I completely missed your previous post.
I could reproduce the issue with Gurobi 9.5.1. I will open a ticket in our support portal so we can investigate this further. Thanks!
0
Please sign in to leave a comment.
Comments
11 comments