How to understand if a dual solution is available
AnsweredHi,
I'm currently using Gurobi to solve a problem and I chose the dual simplex algoritm by setting the Method parameter to 1.
At the end of the optimization I would like to understand if a dual solution is available and to me it's not clear how to achieve this. Looking at the file gurobi_c.h I have found the attribute GRB_INT_ATTR_HASDUALNORM which should return:
- 0 if no dual basis is available;
- 1 if has basis and so can be computed;
- 2 if is already available;
The problem is that at the end of the dual simplex algorithm it always return 0, either when I know a dual solution should exist. This attribute is not explained in the documentation, so maybe it is not implemented yet?
However, there is a better way to understand if a dual solution is available?
Thanks in advance for your attention!
-
Hi Enrico,
You can use the variable and constraint attributes RC (reduced costs) and Pi (dual values) to query those dual solution values.
Please note that these attributes are available for LPs or QPs. You may need to call Model.relax() to relax integrality conditions.
Cheers,
Matthias0 -
Hi Matthias,
thank you for your fast reply!
Just to give you a little insight, I'm working on developing an interface for Gurobi in order to work with our system. I would like to develop a function named has_dual_solution which returns TRUE only if Pi and RC are availabes (without extracting all of them), and in that case with a function named get_dual_solution I will get them using the Gurobi GRBgetdblattr method.
Is there any pre-check that I could use to obtain this information? If not, what will happen if I'll try to extract Pi when it should not be available? Should I expect a DATA_NOT_AVAILABLE return from GRBgetdblattr?
Thank you again for your time,
Enrico
0 -
Hi Enrico,
I would query the status (Optimization Status Codes) and only get the dual solution when it is OPTIMAL (2). Furthermore, you should check that IsMIP is false. That should be sufficient to make sure that there is a dual solution available.
Cheers,
Matthias1 -
Thank you very much for your suggestion!
Cheers,
Enrico
0 -
Hi Matthias,
very sorry to re-open again this request, but I talked with the other members of my team and they asked me if I could dig a little more deeper your suggestion.
In particular, we were talking about the fact that there should be also the possibility to have a dual solution when the model is not solved to the OPTIMAL but is proven to be dual unbounded and so the primary is empty. The idea is that to prove the dual unboundness, you need a dual ray and therefore a dual feasible solution "from which the ray could start". Thus, the condition which states that the status is OPTIMAL maybe could be a little too restrictive.
What do you think of this? Do you know if in the case that the model is proven infeasible (and so dual unbounded) a dual solution still exists?
Best regards,
Enrico
0 -
Hi Enrico!
For that purpose, you would need to query the FarkasDual and FarkasProof attributes. Note that you also need to set the parameter InfUnbdInfo to 1 to get this additional information. This is all described in detail in the linked documentation of those attributes.
I hope that solves your issue.
Cheers,
Matthias0 -
Hi Matthias!
Thank you very much, I have read all the documentation regarding those attributes, but it seems not exactly what I'm looking for. In particular, I don't know how to link the Farkas attributes with the dual solution. The STATUS of the model is what I'm currently searching for (i.e. UNFEASIBLE), but I would like to know if also in this case (as in the OPTIMAL one) there is the possibility of querying for the RC and PI attributes without resulting in some errors. Just to understand if there is the need of adding some more checks in my code.
Thank you again for all your replies!
Best regards,
Enrico
0 -
Hi Enrico,
The Pi and RC attributes are available for infeasible or unbounded models but you need to set the InfUnbdInfo parameter to 1.
I hope that answers your question.
Cheers,
Matthias1 -
Hi Matthias!
Thank you that's very helpful! It is exactly what I was searching for. Just to be sure, the InfUnbndInfo parameter has to be set before the call to GRBoptimize in order to obtain these information, it is correct?
Best regards,
Enrico
0 -
Hi Enrico,
Yes, that's correct! You should be able to set it after the optimization, but then you would need to call optimize() a second time, warm starting from the previous state.
Cheers,
Matthias1 -
Thats perfect! Thank you very much!
0
Please sign in to leave a comment.
Comments
11 comments