Re: [Help-glpk] Dual Cost calculations

[Andrew Makhorin]

> I have been using GLPK to experiment with some Active Constraint methods
> for MIP solving. Several of these methods rely on the dual cost returned 
> by GLPK for individual constraints in a particular node. I am finding 
> that on the nodes of certain problems, GLPK is claiming that every 
> active constraint has a dual cost of zero.
> 
> As such, I was wondering how GLPK is calculating the dual cost, and if 
> this high rate of zero dual costs sounds reasonable?

Standard formulae are used:

Current values of simplex multipliers pi[i], i = 1, ..., m (which
are values of Lagrange multipliers for equality constraints (7) also
called shadow prices) are computed as follows:

   pi = inv(B') * cB,                                            (12)

where B' is a matrix transposed to B, cB is a vector of objective
coefficients at basic variables xB.

Current values of reduced costs d[j], j = 1, ..., n, (which are
values of Langrange multipliers for active inequality constraints
corresponding to non-basic variables) are computed as follows:

   d = cN - N' * pi,                                             (13)

where N' is a matrix transposed to N, cN is a vector of objective
coefficients at non-basic variables xN.

> 
> The problem that this is easiest to examine this on is the "pk1.mps" 
> from the MIPLib2003 problem set. The very first node is returning 15 
> zero-valued dual costs for the first node.

I see nothing unusual. Zero reduced costs just say that the problem is
dual degenerative.


Andrew Makhorin