Re: [Help-glpk] Linear Programming Relaxation

[Ali Baharev]

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