[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: Mon, 30 Nov 2009 16:38:20 +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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]