> 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 _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
