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.
Rdgs,
Paul
________________________________
From: Andrew Makhorin <m...@gnu.org>
To: RC Loh <rc_...@yahoo.com.sg>
Cc: help-glpk@gnu.org
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?
Get your preferred Email name!
Now you can @ymail.com and @rocketmail.com
http://mail.promotions.yahoo.com/newdomains/sg/_______________________________________________
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk
