zero dual variables

[Hossein Haghighat]

hi,

I use AMPL+gubobi for solving a second-order cone optimization problem. to implement a Benders method, I need dual variables from suproblem, but I have noticed that they are all zero. can you please tell me why it does not give dual values?

[T.]

I don't know about SOCP, but in the linear Benders, you do not need the dual variables but the Farkas certificate of infeasibility (which is the dual ray). It is perfectly ok that the dual variables are 0. 

[Greg Glockner]

QCP duals are computationally intensive so they are not returned by default. Set qcpdual=1 in gurobi_options:

http://www.gurobi.com/documentation/6.5/ampl-gurobi/parameters.html

[T.]

Oh, I just realized that I have to correct my above post. In the linear Benders, the duals can be 0 in the case where you want to create a feasibility cut. In the case of feasibility cuts, you do not need the duals, but the dual ray (Farkas certificate). In the case of optimality cuts, you of course need the dual values.

I would expect that it is the same in case of SOCP, but I have to admit that I don't know.

[Hossein Haghighat]

hi,

thank you. but after setting that parameter to 1, it still gives zero dual values. I have checked with other linear solvers. they computes duals but Gurobi does not. 

[T.]

Two questions:

1. Do your variables have non-trivial upper or lower bounds (bounds that are not 0 or +/- infinity)? Then you also have to consider the reduced cost vector as duals.

2. Is the instance where the duals are 0 feasible or infeasible?

[Hossein Haghighat]

hi,

1- yes. they do. 

2- it is feasible if I get your question right.

it seems there is a bug in Gurobi, because it does not compute duals. I have check with other solvers they do give the duals.  

[T.]

2. Ok, then forget about the Farkas certificate that I mentioned above.

1. Then everything might be ok. If your model has several solutions, then it might be perfectly ok to have 0 in all duals of the constraints. Remember that you also have to consider your bounds as constraints (though you don't have to implement them as constraints). Their duals are the reduced costs. If you do not consider them, your implementation is surely wrong. In this case, please re-read the literature.

[Greg Glockner]

I reviewed a copy of the model. There are several issues:

First, as stated before, you must set qcpdual=1 to get QCP duals. However, the model has numerical issues, which prevents it from computing the QCP duals. As a workaround, set numericfocus=3 and qcpdual=1 to get the QCP duals.

Finally, when in doubt, review the Gurobi logs. By default, AMPL does not print the Gurobi logs; add outlev=1 to gurobi_options to get the Gurobi logs.

[Hossein Haghighat]

hello,

thanks for looking into the model. here is my setting that I have used :

option gurobi_options " numericfocus 3 barqcptol 1e-5 intfeastol 1e-7 feastol 1e-7 opttol 1e-7 mipgap 1e-7 qcpdual 1";

[Greg Glockner]

That looks overtuned. Try just numericfocus 3 qcpdual 1.

[Hossein Haghighat]

please note that the model needs that setting. otherwise, the results are not dependable.

[Greg Glockner]

> please note that the model needs that setting. otherwise, the results are not dependable.

That suggests that your model has major numerical issues.

[Hossein Haghighat]

hello,

here is the results of AMPL support investigation on my problem,

When 'outlev 1' is added to the gurobi_options string for the example that you sent us, we see an explicit message that Gurobi is not able to compute dual values:

   Warning: failed to compute QCP dual solution due to inaccurate barrier solution
            Try decreasing BarQCPConvTol for more accuracy

If you decrease the tolerance by setting, say, 'barqcptol 1e-6', then you do get the dual values in many cases, but occasionally the dual computation still fails and also in some cases you get "Sub-optimal termination" and other failure messages.  Thus it seems that there does not exist any robust setting that can be used throughout your decomposition procedure.

This situation difficulty has been reported before, as we can see by going to the Gurobi user group at http://groups.google.com/group/gurobi and searching on "failed to compute QCP dual solution".  The errors occur inside Gurobi so they are not something that can be fixed by us at AMPL.  Perhaps there is a more stable formulation of your model, but that is not something that we could help with since the details of any reformulation would be very specific to your application.

You could send your files to sup...@gurobi.com which might lead to improvements in the next release of Gurobi.  For now, however, it seems you are better off using CPLEX for this particular application.