Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #6917 > unrolled thread

linear programming

Back to article view | Back to comp.lang.c++

Contents

  linear programming eric <cneric12lin0@gmail.com> - 2011-06-19 20:53 -0700
    Re: linear programming "Alf P. Steinbach /Usenet" <alf.p.steinbach+usenet@gmail.com> - 2011-06-20 08:36 +0200
      Re: linear programming eric <cneric12lin0@gmail.com> - 2011-06-20 00:58 -0700
        Re: linear programming "Alf P. Steinbach /Usenet" <alf.p.steinbach+usenet@gmail.com> - 2011-06-20 11:38 +0200
      Re: linear programming gwowen <gwowen@gmail.com> - 2011-06-20 03:07 -0700
        Re: linear programming "Alf P. Steinbach /Usenet" <alf.p.steinbach+usenet@gmail.com> - 2011-06-20 14:09 +0200
          Re: linear programming gwowen <gwowen@gmail.com> - 2011-06-20 05:59 -0700
            Re: linear programming gwowen <gwowen@gmail.com> - 2011-06-20 06:03 -0700
            Re: linear programming Martijn van Buul <pino@dohd.org> - 2011-06-20 15:13 +0000
              Re: linear programming gwowen <gwowen@gmail.com> - 2011-06-20 08:38 -0700
                Re: linear programming Martijn van Buul <pino@dohd.org> - 2011-06-20 19:24 +0000
                  Re: linear programming Gareth Owen <gwowen@gmail.com> - 2011-06-21 06:30 +0100
                    Re: linear programming gwowen <gwowen@gmail.com> - 2011-06-21 00:17 -0700
              [OT] Re: linear programming Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-20 21:56 +0200
                Re: linear programming eric <cneric12lin0@gmail.com> - 2011-06-20 17:27 -0700
    Re: linear programming "Paul" <pchristor@yahoo.co.uk> - 2011-06-20 11:17 +0100
    Re: linear programming gwowen <gwowen@gmail.com> - 2011-06-20 03:07 -0700
    [OT] Re: linear programming Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-20 19:38 +0200

#6917 — linear programming

Dear c++ or advanced computer scienctist or mathmatician:
  on the book(Introduction to Algorithms 3rd ed) page 851, chapter 29
Linear Programming
I ask one of that book's author:
-----------------------------------------------
   dear thomas:

  the the end of that page

 if a linear program has some feasible solutions but does not have a
 finite optimal objective value, we say that the linear program is
 unbounded

 but
 you want us to prove in Exercise 29.1-9
 to show
 that a linear program can have a finite optimal objective value even
if
 the feasible region is not bounded

 which is very unlogical for me

 looking to hear from you soon
 Eric

------------------------------------------------------------------

Eric, you'll have to think outside the box just a little bit.  It may
seem illogical, but there's a simple solution.

Tom Cormen
Professor and Chair
Dartmouth College Department of Computer Science
http://www.cs.dartmouth.edu/~thc/
-----------------------------------------------------
but I still not figure out
plz give hint/suggestion/advice, thank your help/effort/time a lot in
advance, Eric

[toc] | [next] | [standalone]

#6927

* eric, on 20.06.2011 05:53:
> Dear c++ or advanced computer scienctist or mathmatician:
>    on the book(Introduction to Algorithms 3rd ed) page 851, chapter 29
> Linear Programming
> I ask one of that book's author:
> -----------------------------------------------
>     dear thomas:
>
>    the the end of that page
>
>   if a linear program has some feasible solutions but does not have a
>   finite optimal objective value, we say that the linear program is
>   unbounded
>
>   but
>   you want us to prove in Exercise 29.1-9
>   to show
>   that a linear program can have a finite optimal objective value even
> if
>   the feasible region is not bounded
>
>   which is very unlogical for me
>
>   looking to hear from you soon
>   Eric
>
> ------------------------------------------------------------------
>
> Eric, you'll have to think outside the box just a little bit.  It may
> seem illogical, but there's a simple solution.
>
> Tom Cormen
> Professor and Chair
> Dartmouth College Department of Computer Science
> http://www.cs.dartmouth.edu/~thc/
> -----------------------------------------------------
> but I still not figure out
> plz give hint/suggestion/advice, thank your help/effort/time a lot in
> advance, Eric

Let

   A = does not have finite objective value
   B = is unbounded

One statement you're quoting is that A implies B.
This means that in every case where A is true, B will necessarily be true.
Another is that B does not imply A.
This means that in some cases where B is true, A is not true.

For example, if you're out in the rain without any protection, then you get wet.
And in some cases when you get wet, you are not out in the rain without protection.


Cheers & hth., and please post to a relevant group next time!,

- Alf

-- 
blog at <url: http://alfps.wordpress.com>

[toc] | [prev] | [next] | [standalone]

#6932

On Jun 19, 11:36 pm, "Alf P. Steinbach /Usenet" <alf.p.steinbach
+use...@gmail.com> wrote:
> * eric, on 20.06.2011 05:53:
>
>
>
> > Dear c++ or advanced computer scienctist or mathmatician:
> >    on the book(Introduction to Algorithms 3rd ed) page 851, chapter 29
> > Linear Programming
> > I ask one of that book's author:
> > -----------------------------------------------
> >     dear thomas:
>
> >    the the end of that page
>
> >   if a linear program has some feasible solutions but does not have a
> >   finite optimal objective value, we say that the linear program is
> >   unbounded
>
> >   but
> >   you want us to prove in Exercise 29.1-9
> >   to show
> >   that a linear program can have a finite optimal objective value even
> > if
> >   the feasible region is not bounded
>
> >   which is very unlogical for me
>
> >   looking to hear from you soon
> >   Eric
>
> > ------------------------------------------------------------------
>
> > Eric, you'll have to think outside the box just a little bit.  It may
> > seem illogical, but there's a simple solution.
>
> > Tom Cormen
> > Professor and Chair
> > Dartmouth College Department of Computer Science
> >http://www.cs.dartmouth.edu/~thc/
> > -----------------------------------------------------
> > but I still not figure out
> > plz give hint/suggestion/advice, thank your help/effort/time a lot in
> > advance, Eric
>
> Let
>
>    A = does not have finite objective value
>    B = is unbounded
>
> One statement you're quoting is that A implies B.
> This means that in every case where A is true, B will necessarily be true.
> Another is that B does not imply A.
> This means that in some cases where B is true, A is not true.
>
> For example, if you're out in the rain without any protection, then you get wet.
> And in some cases when you get wet, you are not out in the rain without protection.
>
> Cheers & hth., and please post to a relevant group next time!,
>
> - Alf
>
> --
> blog at <url:http://alfps.wordpress.com>

----------------------------------------------
I think you reply a little bit too fast.
Could I ask you, are you computer science/math student/worker?
in that book, that page, that sentence
there is no word(s) (implies)

which part do you think it can be treated as (implies)?
  "We say" ?

 why it can not be treated as (equal or defined it)

even that sentence should be treated as your way (implies) not
mine(equal)
then
Can you show out what is the definition of bounded or unbounded, /*
since we need that definition but authors did not gave out */?

looking to see any computer scientist/mathmatician 's advice/
suggestion/hint and thanks a lot in advance, Eric

[toc] | [prev] | [next] | [standalone]

#6941

* eric, on 20.06.2011 09:58:
> in that book, that page, that sentence
> there is no word(s) (implies)

"if" - "then" expresses an implication

use e.g. Wikipedia to learn about logical implications


cheers & hth., & please next time post in an appropriate group,

- alf

-- 
blog at <url: http://alfps.wordpress.com>

[toc] | [prev] | [next] | [standalone]

#6943

On Jun 20, 7:36 am, "Alf P. Steinbach /Usenet" <alf.p.steinbach
+use...@gmail.com> wrote:
> Let
>
>    A = (the program) does not have finite objective value
>    B = (the program) is unbounded
>
> One statement you're quoting is that A implies B.

That's not right.  The statement he quotes gives B as the *definition*
of A, so A <=> B

[toc] | [prev] | [next] | [standalone]

#6950

* gwowen, on 20.06.2011 12:07:
> On Jun 20, 7:36 am, "Alf P. Steinbach /Usenet"<alf.p.steinbach
> +use...@gmail.com>  wrote:
>> Let
>>
>>     A = (the program) does not have finite objective value
>>     B = (the program) is unbounded
>>
>> One statement you're quoting is that A implies B.
>
> That's not right.  The statement he quotes gives B as the *definition*
> of A, so A<=>  B

An "if-then" is a one way implication, not two-way.

For example, IF the text is so vague/informal as to not make that distinction, 
THEN it's meaningless to ponder very fine details of meaning in the text.


Cheers & hth.,

- Alf

-- 
blog at <url: http://alfps.wordpress.com>

[toc] | [prev] | [next] | [standalone]

#6953

On Jun 20, 1:09 pm, "Alf P. Steinbach /Usenet" <alf.p.steinbach
+use...@gmail.com> wrote:

> > That's not right.  The statement he quotes gives B as the *definition*
> > of A, so A<=>  B
>
> An "if-then" is a one way implication, not two-way.

Usually yes.  But this is phrased like'If "something" satifies
"condition A", then we say it is "A-ified".'  In English-as-she-is-
used-by-mathematicians that's *a definition* of "A-ified". It's two
way. As a native English speaking mathematician, you really should
take me word on this.

e.g. Definition of continuity under arbitrary topologies: "If the
preimage under f() of any open set is itself, we say f() is
continuous".

[toc] | [prev] | [next] | [standalone]

#6954

On Jun 20, 1:59 pm, gwowen <gwo...@gmail.com> wrote:

> e.g. Definition of continuity under arbitrary topologies: "If the
> preimage under f() of any open set is itself, we say f() is
> continuous".

Ooops missed a word ... e.g. Definition of continuity under arbitrary
topologies: "If the preimage under f() of any open set is itself open,
we say f() is continuous".

[toc] | [prev] | [next] | [standalone]

#6959

* gwowen:
> Usually yes.  But this is phrased like'If "something" satifies
> "condition A", then we say it is "A-ified".'  In English-as-she-is-
> used-by-mathematicians that's *a definition* of "A-ified". 

Uh, most mathematicians I know would have used "if and only if" or 
any of its alternatives in that case; in writing it would've been 'iff'.

-- 
Martijn van Buul - pino@dohd.org 

[toc] | [prev] | [next] | [standalone]

#6961

On Jun 20, 4:13 pm, Martijn van Buul <p...@dohd.org> wrote:
> * gwowen:
>
> > Usually yes.  But this is phrased like'If "something" satifies
> > "condition A", then we say it is "A-ified".'  In English-as-she-is-
> > used-by-mathematicians that's *a definition* of "A-ified".
>
> Uh, most mathematicians I know would have used "if and only if" or
> any of its alternatives in that case; in writing it would've been 'iff'.

Not in undergraduate lecture notes, which are much more informal.
Anyway, go find one of the numerous mathematicians of your
acquaintance and ask them what the definition an "unbounded linear
program" is. Then ask them what the definition of "unbounded feasible
region" is.

Alternatively, go and read this incredibly basic introduction to
linear programming -- http://www.caam.rice.edu/~yzhang/caam378/Notes/chap1.pdf
(specifically S1.5 on pg 11)

Then, come back, and admit that I know of what I speak.

[toc] | [prev] | [next] | [standalone]

#6970

* gwowen:
> On Jun 20, 4:13?pm, Martijn van Buul <p...@dohd.org> wrote:
>> * gwowen:
>>
>> > Usually yes. ?But this is phrased like'If "something" satifies
>> > "condition A", then we say it is "A-ified".' ?In English-as-she-is-
>> > used-by-mathematicians that's *a definition* of "A-ified".
>>
>> Uh, most mathematicians I know would have used "if and only if" or
>> any of its alternatives in that case; in writing it would've been 'iff'.
>
> Not in undergraduate lecture notes, which are much more informal.

Your problem, not mine. Don't make any claims then. You're the one who takes
an informal explanation out of context, not me.

> Anyway, go find one of the numerous mathematicians of your
> acquaintance and ask them what the definition an "unbounded linear
> program" is. Then ask them what the definition of "unbounded feasible
> region" is.

Irrelevant. I didn't question the validity of that statement. I questioned
the validity of your "argument".

> Then, come back, and admit that I know of what I speak.

Oh, I'll admit what I already know:

You're awfully full of yourself, but have very little to show. But that 
applies to a lot of people here, so you're in good company.

-- 
Martijn van Buul - pino@dohd.org 

[toc] | [prev] | [next] | [standalone]

#6990

Martijn van Buul <pino@dohd.org> writes:

>> Anyway, go find one of the numerous mathematicians of your
>> acquaintance and ask them what the definition an "unbounded linear
>> program" is. Then ask them what the definition of "unbounded feasible
>> region" is.
>
> Irrelevant. I didn't question the validity of that statement. I questioned
> the validity of your "argument".

You don't understand what "we say" means in this context.  That's OK.
It's not your first language, and its not your field of expertise. You
made an entirely forgiveable mistake.

But please have the humility not to "correct" someone for whom it *is*
there first language, in their field of expertise, and then accuse
*them* of being full of themselves.

Because that is *not* a forgiveable mistake.

[toc] | [prev] | [next] | [standalone]

#6992

On Jun 21, 6:30 am, Gareth Owen <gwo...@gmail.com> wrote:

> But please have the humility not to "correct" someone for whom it *is*
> there first language,
  ^^^^^

Ha! Skitt's Law strikes again.

[toc] | [prev] | [next] | [standalone]

#6973 — [OT] Re: linear programming

Martijn van Buul wrote:

> * gwowen:
>> Usually yes.  But this is phrased like'If "something" satifies
>> "condition A", then we say it is "A-ified".'  In English-as-she-is-
>> used-by-mathematicians that's *a definition* of "A-ified".
> 
> Uh, most mathematicians I know would have used "if and only if" or
> any of its alternatives in that case; in writing it would've been 'iff'.

That does not match my experience. In _defintions_ you don't say "if and 
only if". Examples:

  A group G is called commutative or abelian if ab=ba for all a,b in G.

Or:

  A group G is called commutative or abelian if its group law is 
  commutative.

I am not aware of a mathematician who would use "if and only if" within a 
definition, e.g.:

  A group G is called abelian if and only if ab=ba for all a,b in G.

Of course, there is this mixture of theorem and definition, where you say 
something like: "For a ring R, the following three conditions are equivalent 
...; if any of them holds for R, we call R noetherian." Note, however, the 
"if" in the definition part of that statement. This is, what I think feels 
most natural to a mathematician.


To verify this point, you can check for instance in the following standard 
literature for the definition of a commutative group:

  Isaacs: Algebra, a graduate course (page 11)
  Bourbaki: Elements of Mathematic, Algebra 1 Chapters 1 - 3; 
            1.4.2 (page 31)
  Lang: Algebra (3rd ed), page 4 bottom
  Rotman: Advanced Modern Algebra; Groups I Chapter 2 page 52

In all cases, you will find "if" used instead of "if and only if". I cite 
those books not (just) as an apeal to authority. The graduate courses based 
upon those books shape the mathematical jargon of trained mathematicians. 
Hence, linguistic inclinations are picked up from those patterns.


Of course when it comes to theorems, mathematicians do distinguish very 
precisely a mere implication from an equivalence.



Best,

Kai-Uwe Bux

[toc] | [prev] | [next] | [standalone]

#6986

On Jun 20, 12:56 pm, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
> Martijn van Buul wrote:
> > * gwowen:
> >> Usually yes.  But this is phrased like'If "something" satifies
> >> "condition A", then we say it is "A-ified".'  In English-as-she-is-
> >> used-by-mathematicians that's *a definition* of "A-ified".
>
> > Uh, most mathematicians I know would have used "if and only if" or
> > any of its alternatives in that case; in writing it would've been 'iff'.
>
> That does not match my experience. In _defintions_ you don't say "if and
> only if". Examples:
>
>   A group G is called commutative or abelian if ab=ba for all a,b in G.
>
> Or:
>
>   A group G is called commutative or abelian if its group law is
>   commutative.
>
> I am not aware of a mathematician who would use "if and only if" within a
> definition, e.g.:
>
>   A group G is called abelian if and only if ab=ba for all a,b in G.
>
> Of course, there is this mixture of theorem and definition, where you say
> something like: "For a ring R, the following three conditions are equivalent
> ...; if any of them holds for R, we call R noetherian." Note, however, the
> "if" in the definition part of that statement. This is, what I think feels
> most natural to a mathematician.
>
> To verify this point, you can check for instance in the following standard
> literature for the definition of a commutative group:
>
>   Isaacs: Algebra, a graduate course (page 11)
>   Bourbaki: Elements of Mathematic, Algebra 1 Chapters 1 - 3;
>             1.4.2 (page 31)
>   Lang: Algebra (3rd ed), page 4 bottom
>   Rotman: Advanced Modern Algebra; Groups I Chapter 2 page 52
>
> In all cases, you will find "if" used instead of "if and only if". I cite
> those books not (just) as an apeal to authority. The graduate courses based
> upon those books shape the mathematical jargon of trained mathematicians.
> Hence, linguistic inclinations are picked up from those patterns.
>
> Of course when it comes to theorems, mathematicians do distinguish very
> precisely a mere implication from an equivalence.
>
> Best,
>
> Kai-Uwe Bux
-----------------
Dear Kai-Uwe Bux:

  I am waiting these 4 authores reply my email about this question.  I
hope their explanation/sulution match your suggestion/interpretation.
  And no matter what is these 4 authores going to reply me, I thanks a
lot your help.

sincerely, Eric
-----------------

[toc] | [prev] | [next] | [standalone]

#6942

"eric" <cneric12lin0@gmail.com> wrote in message 
news:12e289fe-86ca-4bd3-b391-9a1a4005476f@22g2000prx.googlegroups.com...
> Dear c++ or advanced computer scienctist or mathmatician:
>  on the book(Introduction to Algorithms 3rd ed) page 851, chapter 29
> Linear Programming
> I ask one of that book's author:
> -----------------------------------------------
>   dear thomas:
>
>  the the end of that page
>
> if a linear program has some feasible solutions but does not have a
> finite optimal objective value, we say that the linear program is
> unbounded
>
> but
> you want us to prove in Exercise 29.1-9
> to show
> that a linear program can have a finite optimal objective value even
> if
> the feasible region is not bounded
>
> which is very unlogical for me
>
Maybe a 'feasible region' is not bounded but the progam is bounded. 

[toc] | [prev] | [next] | [standalone]

#6944

On Jun 20, 4:53 am, eric <cneric12l...@gmail.com> wrote:

>  if a linear program has some feasible solutions but does not have a
>  finite optimal objective value, we say that the linear program is
>  unbounded

Here, he's talking about the linear program being unbounded.

> if the feasible region is not bounded

Here, he's talking about the feasible region being unbounded.
They're not the same thing.

Guru Meditation: Maximise (7-x) subject to (x>0).

[toc] | [prev] | [next] | [standalone]

#6964 — [OT] Re: linear programming

eric wrote:

> Dear c++ or advanced computer scienctist or mathmatician:
>   on the book(Introduction to Algorithms 3rd ed) page 851, chapter 29
> Linear Programming
> I ask one of that book's author:
> -----------------------------------------------
>    dear thomas:
> 
>   the the end of that page
> 
>  if a linear program has some feasible solutions but does not have a
>  finite optimal objective value, we say that the linear program is
>  unbounded
> 
>  but
>  you want us to prove in Exercise 29.1-9
>  to show
>  that a linear program can have a finite optimal objective value even
> if
>  the feasible region is not bounded
> 
>  which is very unlogical for me

Notice the difference between

a) a program is unbounded.
b) a program has an unbounded feasible region. 

Any unbounded program has an unbounded feasible region. The exercise asks 
you to give an example showing that the converse does not hold. For this, 
think geometrically and draw some linear programs in dimension 2. You can 
find such examples there.


Best,

Kai-Uwe Bux

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web