Conic optimization with second-order cone - MIP finds a better solution than relaxation
AnsweredI am solving an assortment optimization problem for an academic study. I first formulate an IP, then get the continuous relaxation. As the problem is non-polynomial, I formulate it using second order cone constraints and solve it using Gurobi. Here is the problem: under the exact same code, when I change the assignment variable from 'C' (0<=x_ij<=1) to 'I' (x_ij \in {0,1}), solver finds a better solution. This should not technically be possible as the relaxation is a natural upper bound. I thought this could be about the tolerances but even with the smallest tolerance setting, I do not seem to fix this issue.
Is there something I am missing? What could be the reason for this issue?
-
-
Gurobi Staff
Hi Mert,
This might happen if the model is subject to numerical challenges.
Could you please share an MPS file of your model through Google Drive, Dropbox, or OneDrive? We can then investigate the issue you observed further. Please also include in your response the variable names whose types change from continuous to binary.
Best regards,
Maliheh
0 -
-
Hello Maliheh,
Thank you for your response! I am a Mac user, thus I am using R API for Gurobi operations.
In the link below, you can find the R script I am using along with a pdf file that shows the model I am trying to solve. The variable that I change from continuous to binary is x_js. There are comments in the script, so it should not be hard to find.https://drive.google.com/drive/folders/1ufMSWzF903w9tZfXwXGJPbM8eik4bQUh?usp=share_link
Best,
Mert
0 -
-
-
Thanks for the files, but I need to be able to run the code and replicate the behaviour you described. I cannot run your R script because some of the input objects and functions such as \(\texttt{stores}\), \(\texttt{products}\), and \(\texttt{spMatrix}\) are not found.
Please run your code and save the model into a file using the gurobi_write(model, "model.lp") method (you can add this before calling the gurobi(model, params) method). You can then share the model file named as \(\texttt{model.lp}\) with us.
Best regards,
Maliheh
0 -
-
Thank you for the guidance. I have added "model.lp" to the same Google Drive file.
Best,
Mert
0 -
-
-
Thanks for uploading the model file.
- Solving the continuous model gives the optimal objective value of ~9.8306e+01.
- Relaxing the continuous variables \(x\) and solving it as an MIQCP instance results in the optimal objective value of 104.237. This is greater than 9.8306e+01 as we expect for a minimization problem.
In the log of MIQCP instance, we have:
Root relaxation: objective 4.340145e+01, 2 iterations, 0.00 seconds (0.00 work units)
I assume your question is why the relaxation value is not equal to 9.8306e+01. This is because Gurobi solves an MIQCP instance in different presolved formats controlled by the PreMIQCPForm parameter.
If you set the parameter PreMIQCPForm=1, Gurobi will transform the quadratic constraints to second-order cone constraints and you will see the line below in the log:
Root relaxation: objective 9.830629e+01, 0 iterations, 0.04 seconds (0.00 work units)
Please note that regardless of the setting chosen for the PreMIQCPForm parameter, the optimal solution for the MIQCP instance is 104.237.
Best regards,
Maliheh
0 -
Please sign in to leave a comment.
Comments
5 comments