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

[Robbie Morrison]

------------------------------------------------------------
To:          address@hidden
Subject:     RE: [Help-glpk] optimality conditions paragraph
             (KKT and LP formulations)
Message-ID: <address@hidden>
From:        Andrew Makhorin <address@hidden>
Date:        Wed, 11 May 2011 22:21:24 +0400
------------------------------------------------------------

> 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

Hello Andrew

I now interrogate the 'LPXKKT' struct, with logic
gleaned from the code in 'src/glpapi11.c'.  I was
puzzled for quite a while as to why some GLPSOL reports
offered all four KKT conditions and others only two.
The latter were, of course, MIP instances. And on
closer inspection, the reports are labeled differently:

  Karush-Kuhn-Tucker optimality conditions:
  Integer feasibility conditions:

I quite agree about keeping the GLPK wikibook strictly
interpretive.  It should not unthinkingly replicate the
GLPK manuals, nor it should provide theory much beyond
the odd pointer for orientation.

Let's wait a week or so and then I should return the
editing the KKT section, using the above guidelines and
the various contributions from this list.

thanks to everyone for their time and info, cheers
---
Robbie Morrison
PhD student -- policy-oriented energy system simulation
Technical University of Berlin (TU-Berlin), Germany
University email (redirected) : address@hidden
Webmail (preferred)           : address@hidden
[from Webmail client]