[SciPy-User] How to check inequalities for contradiction

[Dominique Orban]

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.

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.

-- 
Dominique