help-glpk
[Top][All Lists]

## Re: [Help-glpk] Dual Cost calculations

 From: Andrew Makhorin Subject: Re: [Help-glpk] Dual Cost calculations Date: Thu, 13 Jul 2006 17:14:30 +0400

```> 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

```