[SciPy-User] How to check inequalities for contradiction

[Bastian Weber]

Thanks a lot for that explanation.

As m and n are rather small in my case runtime is not an issue.
To avoid the effort that comes along with new libraries I tried to solve
the problem by myself only using numpy and the standard lib.

Therefore using itertools I construct all combinations of n elements of
the set range(m). To each combination correspond n inequalities. If I
interpret these as equations, i.e. substituting ">" with "=" and solve
that linear system, I get a point. I call it a 'candidate vertex'. If
this candidate vertex fullfills the m-n inequalities which were not used
for its calculation, then it is indeed a vertex of the solution region.
If it does not then it can be dismissed.

If finally the list of valid vertices has a length > 0, the inequalities
 do not contradict.

It seems to work, although it seems to be a naive approach.

As this is only a part of a bigger problem, the package NLPy seems to be
very interesting. So thanks again for this hint.

Cheers.
Bastian.


Dominique Orban wrote:

> Hi Bastian,
>
> This problem is as complicated as the linear programming problem
> (http://en.wikipedia.org/wiki/Linear_programming). Your particular
> instance has a vector c identically equal to zero. Strangely, having
> c=0 doesn't make the problem any easier. There are methods out there
> that can solve the problem in polynomial time (where "time" is linear
> in the total length of the input data, i.e., the matrix A and the
> vector b). Those methods are called "interior-point methods". There
> are other methods, such as the simplex method, which are in principle
> not polynomial, although in practice, good implementations are
> effective.
>
> Both types of methods are implemented in GLPK. PuLP provides a Python
> interface to GLPK: http://code.google.com/p/pulp-or.
> There is also an interior-point method in NLPy: nlpy.sf.net
>
> So yes, there are out-of-the-box solution methods.
>



> On Tue, Nov 2, 2010 at 8:20 PM,  <scipy-user-request at scipy.org> wrote:
> 
>> From: Bastian Weber <bastian.weber at gmx-topmail.de>
>> To: SciPy Users List <scipy-user at scipy.org>
>> Date: Tue, 02 Nov 2010 18:46:57 +0100
>> Subject: [SciPy-User] How to check inequalities for contradiction
>> Hi,
>>
>>
>> I have a System of inequalities like this
>>
>>
>> Ax + b >= 0
>>
>>
>> where the Relation ">=" is meant to hold in every line of the equation
>> system. Additionally, every element of x has to be nonnegative.
>>
>> Say
>>
>> m,n = A.shape
>>
>> thus
>>
>> len(x) == n
>> len(b) == m
>>
>> I have m > n.
>>
>> What would be the preferred way to test whether a solution exists?
>> In other words, I want to test that there is no contradiction in the
>> system of inequalities.
>>
>>
>> The main intention of this post is to figure out whether a
>> out-of-the-box solution to this type of problems exists.
>>
>> Thanks in advance.
>> Bastian.
>