Re: [Help-glpk] Linear Programming Relaxation

[Andrew Makhorin]

>> 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.