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