[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: Mon, 30 Nov 2009 17:17:58 +0800 (SGT)

Hi Andrew, Jeffrey, Michael,
Thank you very much for your responses.
I will read up on Special Ordered Set (SOS) as suggested by Micheal. Because SOS is new to me.
Hi Jeffrey,
What I am trying to obtain is that though using LPR, the solution is bounded, but the solution does not satisfy what I need which is "x1+x2<=1" which means that "x1" and "x2" cannot co-exist together in a solution.
Without using LPR, that is, the "x1" and "x2" are binaries, then the solution obtained by LP is correct.
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.
What I want is that "x1" and "x2" CANNOT co-exist together in the solution.
And I understand that LP runs in exponential time, however, LPR can run in polynomial time.
That is why, I want to use LPR.  
Any suggestion or idea is appreciated.

From: Andrew Makhorin <address@hidden>
To: RC Loh <address@hidden>
Cc: address@hidden
Sent: Monday, 30 November 2009 2:22:36
Subject: Re: [Help-glpk] Linear Programming Relaxation

> However, I was pondering for the last 2 days about your response. It
> seems to me that the global bound is not much use for my problem.
> Because the global will give an *upper bound* for the reliability and
> bandwidth which is of no use. A *lower bound* will be more useful. So

In case of minimization (like yours) optimal solution to LP relaxation
is just an lower bound to the exact integer optimum while an upper bound
is the one defined by any integer feasible solution. That is, the
following condition always holds:

  lower_bound <= exact_optimum <= upper_bound

> I was trying to formulate the problem to try to get a *lower bound*,
> but until now I am not successful of doing it.

Once you have solved LP relaxation, you have got an lower bound.

> Another question if you do not mind.

No, I don't.

> Actually the constraint of "x1+x2<=1" is to prevent x1 and x2 to
> co-exists together in the solution. If x1 and x2 are binary, then GLPK
> can produce a good solution.

> However, if I will to use LPR, then GLPK gave a solution such that x1
> and x2 *can* co-exists together in the solution, which is not what I
> want. Is there a way to prevent this? That is, even if LPR is used I
> can prevent x1 and x2 to co-exists together in the solution?

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?

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]