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

[Meketon, Marc]

Many books call the min c'x, s.t. Ax=b, x>=0 form the "canonical" linear 
programming program.  The min c'x s.t. Ax >= b, x>=0 is often called the 
"standard" form, because it has more symmetry with the dual (which is max b'y 
s.t. A'y<=c, y>=0).  But I've never heard it call the "augmented" form until I 
googled it and found it in the wikipedia.

Googling "Canonical linear programming problem" brings up a number of web-sites 
that agree with the min c'x, s.t. Ax=b, x>=0 form such as
http://web.williams.edu/go/math/sjmiller/public_html/399/handouts/LinearProgramming.pdf
http://cis.poly.edu/POG/canon.pdf
And some of the textbooks I have at home also use "canonical" in that way.

However, some websites use the min c'x Ax >= b, x >=0 to be the canonical form
http://www.math.ucla.edu/~rfb/164.1.07s/midsol.pdf

And some websites use max c'x s.t. Ax <= b, x >= 0 to be the canonical form
http://www.cs.uiuc.edu/class/fa05/cs473g/lectures/17-lp.pdf
http://en.wikipedia.org/wiki/Linear_programming#Standard_form (actually, this 
wikipedia article is misleading in that it calls this form the "canonical form" 
at the beginning of the article, and the "standard" form a few paragraphs 
below, where the only difference is that the standard form has b>=0;)

The wikipedia article is where you probably picked up the "augmented" which, 
while in equality form, is really referring to augmenting the Ax<=b formulation 
with slack variables.  And it seems (I could be wrong about this) that only the 
wikipedia article uses that word.

So, please change "augmented" to either "canonical" (which is my preference) or 
"standard" (which is Andrew's preference).

-----Original Message-----
From: Robbie Morrison [mailto:address@hidden
Sent: Thursday, May 12, 2011 8:40 AM
To: Andrew Makhorin
Cc: GLPK help; Meketon, Marc
Subject: RE: [Help-glpk] optimality conditions paragraph (KKT and LP 
formulations)


Hello Andrew, also Marc and the list

------------------------------------------------------------
To:          Robbie Morrison <address@hidden>
Subject:     RE: [Help-glpk] optimality conditions paragraph (KKT and LP
formulations)
Message-ID: <address@hidden>
From:        Andrew Makhorin <address@hidden>
Date:        Thu, 12 May 2011 12:08:03 +0400
------------------------------------------------------------

> Hi Robbie,
>
> [snip: earlier post]
>
> Probably to make the glpk wikibook paragraph about the KKT conditions
> complete, the text following below could be included there (' means
> transposition).
>
> Best regards,
>
> Andrew Makhorin
>
> Original (primal) LP problem in the standard format:
>
>    minimize  z = c'x
>
>    s.t.     Ax = b
>
>              x >= 0
>
> where x is a vector of primal variables.

[snip: remainder of post]

---------------------------------
 KKT theory
---------------------------------

The new mark-up is here:

  
http://en.wikibooks.org/wiki/Talk:GLPK/Solution_information#Karush-Kahn-Tucker_theory

A couple of small points (which can be easily reversed):

  * used the term "augmented form" instead of "standard format"

  * changed (pi, lambda) to (pi | lambda) for the vector concatenation

  * added a final sentence on MIP use

Thanks too to Marc for his encouragement.

---------------------------------
 Status "B"
---------------------------------

One other thing, somewhat related.  From the same page describing the various 
GLPK human-readable reports.

More specifically, the 'glp_print_sol' solution report, also accessible via the 
GLPSOL '--output' option.  For an example, please see:

  http://en.wikibooks.org/wiki/GLPK/Interoperability#GLPSOL_output_format

What does 'B' in the 'St' status column indicate?

Is this identical to the 'BS' in the same column, in the sensitivity analysis 
report produced by 'glp_print_ranges' and the '--ranges' option?  For an 
example, see:

  http://en.wikibooks.org/wiki/GLPK/Interoperability#GLPSOL_sensitivity_analysis

  BS = constraint inactive

In addition, there can be "< eps" comments.  For close-to-zero values, I guess. 
 What is the threshold?
Is this threshold user-modifiable?  If so, how can it be reset?

Also, often the 'Lower bound' and 'Upper bound' entries are missing, I suppose 
this implies -inf and +inf, respectively?

best wishes to all
---
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]



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.