[SciPy-User] How to check inequalities for contradiction
Bastian Weber
bastian.weber@gmx-topmail...
Thu Nov 4 10:40:08 CDT 2010
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@scipy.org> wrote:
>
>> From: Bastian Weber <bastian.weber@gmx-topmail.de>
>> To: SciPy Users List <scipy-user@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.
>
More information about the SciPy-User
mailing list