Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations)

[Andrew Makhorin]

Dear Robert,

> I have been watching this thread and have grown concerned that some serious
> errors are creeping in.  So as a start I have made several corrections that
> I hope you will not mind.  In particular I would note that: (1) the
> optimality condition for LP is strong duality, not weak duality; (2)
> complementary slackness is the special case of the KKT conditions when
> applied to linear programming, but strong duality is a different condition
> that is specific to LP; (3) neither of these optimality conditions is
> applicable to mixed-integer programming.

Thank you for your comments.

I don't see any reason to include material from the LP theory in the
glpk wikibook. If somebody is not familiar with the theory, it is
impossible to explain the KKT conditions in few words. I also don't see
a reason to duplicate textbook material, because it would be a useless
job. On the other hand, the knowledgeable user can find all necessary
details on the KKT conditions as they are derived for glpk problem
format, used in, and reported by glpk api routines in the glpk reference
manual, Section "Advanced API Routines". As to mip, I think that Robbie
was confused because of insufficiently clear documentation: in glpk the
structure LPXKKT is also used in api routines to check integer
feasibility of a mip solution, in which case, of course, no integer
optimality conditions are assumed.

Best regards,

Andrew Makhorin