Re: [Help-glpk] 'not' or 'or' constraints?

[Michael Hennebry]

On Fri, 27 May 2005, Stefan Balev wrote:

> Philip Warner wrote:
> >
> > This may not be the right forum for this, but I need to solve an LP
> > problem that is subject to constraints like:
> >
> >    s <= 0 OR s >= 100
> >
> > or, rewritten,
> >
> >    Not (0 < s < 100)
> >
> > Is this something I can do in GLPK?

> A standard remedy consists in introducing a binary variable x in {0,1}
> together with the constraints
>
> s <= M x
> s >= 100 + M (x - 1)
>
> where M is "sufficiently large". This is a MIP problem and can be
> handled by glpk.

It's worth noting that M should be as small
as possible and still be sufficiently large.
This increases the tightness of the linear relaxation.
Obtaining such is mostly left as an exercise for the reader.
Without bounds on s, no M is large enough.

-- 
Mike   address@hidden
"There are three kinds of people,
those who can count and those who can't."