[Top][All Lists]

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

Re: [Help-glpk] Linear Programming Relaxation

From: RC Loh
Subject: Re: [Help-glpk] Linear Programming Relaxation
Date: Tue, 1 Dec 2009 18:32:33 +0800 (SGT)

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.

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


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


New Email names for you!
Get the Email name you've always wanted on the new @ymail and @rocketmail.
Hurry before someone else does!
reply via email to

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