Hi Andrew, Jeffrey,
Thank you for your suggestion. I am currently reading up on SOS1 and see
whether it is applicable to my problem.
However, I have another question to clarify.
According to Andrew, the SOS1 is implemented by a version of Simplex Method.
Then what is the difference between using SOS1 with the Simplex Method compared
to using Integer Programming?
Integer Programming is also using the Simplex Method, isn't it?
Rdgs,
Paul
________________________________
From: Andrew Makhorin <m...@gnu.org>
To: rc_...@yahoo.com.sg
Cc: help-glpk@gnu.org
Sent: Tuesday, 1 December 2009 5:34:27
Subject: Re: [Help-glpk] Linear Programming Relaxation
>> 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.
>
> In mathematics "x1+x2<=1" does not mean "that x1 and x2 cannot co-exist
> together in a solution"; it means that the sum of x1 and x2 is not
> greater than 1. The constraint you need is "NOT x1 OR NOT x2"; this
> constraint is *not* equivalent to "x1+x2<=1" until x1 and x2 are
> restricted to be binary, and being non-convex this constraint cannot be
> modeled within linear program (LP). If you restrict some variables to
> be binary, you get integer program (MIP), not LP.
I would like to add that there exists a version of the simplex method
(which is not implemented in glpk), where you can declare a set of
variables {x1, x2, ..., xk} to be so called Special Ordered Set of
Type 1 (SOS1 for brevity). SOS1 means that at most one of its variables
can be basic while all its other variables must be non-basic. Assuming
that all variables are non-negative, i.e. xj >= 0, SOS1 then means that
at most one of its variables can take non-zero value while values of its
other variables must be zero. Processing SOS1 constraints can be easily
embedded into the simplex method: if some SOS1 variable is basic,
a non-basic variable from the same SOS1 must not be chosen to enter the
basis. However, in general case such version of the simplex method can
find only a local optimum, because SOS1 constraints are non-convex.
New Email names for you!
Get the Email name you've always wanted on the new @ymail and @rocketmail.
Hurry before someone else does!
http://mail.promotions.yahoo.com/newdomains/sg/_______________________________________________
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk
