Re: [Help-glpk] Linear Programming Relaxation

[Jeffrey Kantor]

On Tue, Dec 1, 2009 at 5:41 AM, RC Loh <address@hidden> wrote:
> 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?

Yes and No.  Integer programming typically involves the iterative
addition of constraints that eventually force the solution of a linear
programming problem to have integer values where desired. You
generally need to solve many linear programming problems in the course
of finding a solution to an MIP problem.

The particular method you use to solve the LP's is therefore a choice
-- which can be a simplex method.  You could use an interior point
method, so you could do integer programming without invoking a simplex
routine.

>
> Rdgs,
> Paul
>
> ________________________________
> From: Andrew Makhorin <address@hidden>
> To: address@hidden
> Cc: address@hidden
> 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.
>
>
> ________________________________
> Get your new Email address!
> Grab the Email name you've always wanted before someone else does!