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:[email protected]] Sent: Tuesday, December 28, 2010 5:54 PM To: Meketon, Marc Cc: [email protected] 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. _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
