RE: [Help-glpk] The "dual" suffix and sensitivity to how a constraint is expressed in GMPL

[Meketon, Marc]

I have the following difficulties:

(1) To me, if the primal problem is min c*x s.t. Ax=b, x>=0, I expect the dual 
to be max b*y s.t. yA <= c.  In my case, the rhs, b, is a vector of all 1's; I 
was counting on the fact that the sum of the optimal duals would be equal to 
the primal objective value and was surprised that it wasn't.  Although I 
understand why GMPL changed the sign of the coefficients, it's not intuitive 
and took a little time to investigate why.

(2) The concept that the dual value is the change in the objective function 
with respect to the change in the rhs constraint is misleading when there is 
primal degeneracy and you need to examine the range of subgradients.  This 
occurs because the dual typically has multiple optimal when the primal is 
degenerate.  I'm a bit rusty on this, but I believe that needing to examine a 
range of subgradients extends into the reduced costs of the primal variables as 
well. So the formula dz = r * dx tends to oversimplify what really happens.

To me, the only issues are:
(a) Should GMPL be more clever and check if all the variables are only on one 
side of the constraint, and if so always place the variables on the left-side, 
and the constant on the right side, and not multiply by -1?  That would create 
more intuitive dual variables.

(b) Should the GMPL documentation be more clear?  Maybe the documentation 
should suggest that the ".val" be checked on the constraint to see if any sign 
reversal took place (with a quick example to indicate why).

-----Original Message-----
From: Andrew Makhorin [mailto:address@hidden
Sent: Tuesday, December 28, 2010 5:54 PM
To: Meketon, Marc
Cc: address@hidden
Subject: Re: [Help-glpk] The "dual" suffix and sensitivity to how a constraint 
is expressed in GMPL


...

Do you agree that a*x = b and 2*a*x = 2*b are different constraints (though 
they define identical feasible regions)? Constraints a*x = b and -a*x = -b are 
different for the same reason. In glpk reduced costs are Lagrange multipliers 
defined by the dual equalities, so there is no "freedom" to change their signs. 
The common rule used in glpk is the
following: reduced cost r is a change in the objective function z per unit 
change in corresponding (auxiliary or structural) variable x, that is, dz = r * 
dx, independently on whether z is minimized or maximized.

----------------------------------------------------------------------------
This e-mail and any attachments may be confidential or legally privileged.  If 
you received this message in error or are not the intended recipient, you 
should destroy the e-mail message and any attachments or copies, and you are 
prohibited from retaining, distributing, disclosing or using any information 
contained herein.  Please inform us of the erroneous delivery by return e-mail.

Thank you for your cooperation.
----------------------------------------------------------------------------


This e-mail and any attachments may be confidential or legally privileged. If 
you received this message in error or are not the intended recipient, you 
should destroy the e-mail message and any attachments or copies, and you are 
prohibited from retaining, distributing, disclosing or using any information 
contained herein.  Please inform us of the erroneous delivery by return e-mail. 
Thank you for your cooperation.