dual degeneracy

[Gary]

Hi, Gurobi user,

I have two questions need your help:

1, In Gurobi, is there any way I can flag the constraints that have dual degeneracy, i.e., the constraints that have multiple shadow price?

2, If a constraint has a shadow price, let's say, 100$, I relax that constraint by 1, but the cost change is quite different from 100$, is that possibly because the dual degeneracy?

Regards

[Tobias Achterberg]

A constrait is dual degenerate if it is non-basic but still has a dual solution
value (shadow price) of 0.

The dual solution value just provides a bound on the objective change. The true
objective change can be smaller.

Consider the following example:

max x1
s.t. x1 <= 1 (c1)
x1 <= 1 (c2)

Note that we have two identical constraints. This problem has multiple optimal
bases, one of which being x1 and c1 non-basic and c2 basic. The primal solution
is x1 = 1, the dual solution for this basis is y1 = 1 and y2 = 0.

This means that increasing the right hand side of c1 may increase the optimal
objective value by at most y1 = 1. But it could be less. In this case, we would
not gain anything, because the modified model

max x1
s.t. x1 <= 2 (c1')
x1 <= 1 (c2)

still has an optimal objective value of 1. This is because the previous basis
will no longer stay dual feasible when you increase the right hand side of c1
and thus, a basis switch occurs. You can query the sensitivity information
through the various "SA..." attributes in Gurobi to get information about the
ranges in which the current optimal solution remains optimal.


Regards,

Tobias