[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Meketon, Marc
Subject: Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations)
Date: Thu, 12 May 2011 08:06:15 -0500

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
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

And some websites use max c'x s.t. Ax <= b, x >= 0 to be the canonical 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 

Hello Andrew, also Marc and the list

To:          Robbie Morrison <address@hidden>
Subject:     RE: [Help-glpk] optimality conditions paragraph (KKT and LP
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:

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:

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:

  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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]