Re: [Help-glpk] Linear Programming Relaxation

[Jeffrey Kantor]

You might try this reference:

Smoothed analysis of algorithms: Why the simplex algorithm usually
takes polynomial time -
DA Spielman, SH Teng - Journal of the ACM (JACM), 2004 - portal.acm.org

available here: http://arxiv.org/pdf/cs/0111050   The introduction to
this paper gives an outstanding discussion of the issues of complexity
in the simplex method.  The body of the paper is very dense, but the
introduction is well worth reading for anyone interested in simplex
methods.

Jeff



On Tue, Dec 1, 2009 at 5:32 AM, RC Loh <address@hidden> wrote:
> Hi Ali,
>
> Thank you for your response.
>
> I was trying to find in the Internet under which conditions did the Simplex
> Method runs in polynomial time but I could not find anything.
>
> Can you direct me to some papers or web site that indicate under which
> conditions will the Simplex Method runs in polynomial time?
>
> Thank you.
>
> Rdgs,
> Paul
>
> ________________________________
> From: Ali Baharev <address@hidden>
> To: RC Loh <address@hidden>
> Cc: address@hidden
> Sent: Monday, 30 November 2009 7:50:47
> Subject: Re: [Help-glpk] Linear Programming Relaxation
>
> Hi,
>
>> However, when I did the LPR, "x1" and "x2" can become "0.5". Though it
>> still
>> satisfies the constraint "x1+x2<=1", but that is NOT what I want.
>
> Please re-read Andrew's e-mail:
>
>> LP relaxation is just an LP problem, where all variables are allowed
>> to take any *continuous* values, if only they are satisfied to all LP
>> constraints. You require that x1 + x2 <= 1 but do not require that
>> x1 and x2 are integer-valued, so why do you surprise that you get
>> x1 = x2 = 0.5? Aren't these values satisfy to x1 + x2 <= 1?
>
> Please answer his questions.
>
> You have no choice but to declare those variables binary in order to
> achieve what you want.
>
>> And I understand that LP runs in exponential time, however, LPR can run in
>> polynomial time.
>
> Correction: the simplex method shows exponential complexity in the
> worst case. In practice, it runs in polynomial time. This is
> theoretically proven (under certain conditions).
>
> Have you actually faced performance problems with your problems?
>
> Good luck anyhow,
>
> Ali
>
> ________________________________
> New Email names for you!
> Get the Email name you've always wanted on the new @ymail and @rocketmail.
> Hurry before someone else does!
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk
>
>