[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Linear Programming Relaxation
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Linear Programming Relaxation |
Date: |
Tue, 1 Dec 2009 12:34:27 +0300 |
>> 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.
- Re: [Help-glpk] Linear Programming Relaxation,
Andrew Makhorin <=
- Re: [Help-glpk] Linear Programming Relaxation, RC Loh, 2009/12/01
- Re: [Help-glpk] Linear Programming Relaxation, Jeffrey Kantor, 2009/12/01
- Re: [Help-glpk] Linear Programming Relaxation, Michael Hennebry, 2009/12/01
- Re: [Help-glpk] Linear Programming Relaxation, RC Loh, 2009/12/02
- Re: [Help-glpk] Linear Programming Relaxation, Michael Hennebry, 2009/12/02
- Re: [Help-glpk] Linear Programming Relaxation, Jeffrey Kantor, 2009/12/02
- RE: [Help-glpk] Linear Programming Relaxation, Meketon, Marc, 2009/12/02
- Re: [Help-glpk] Linear Programming Relaxation, Andrew Makhorin, 2009/12/02
- [Help-glpk] Binary Integer Program with Lagrange Multipliers, RC Loh, 2009/12/19
- Re: [Help-glpk] Binary Integer Program with Lagrange Multipliers, Andrew Makhorin, 2009/12/20