Algorithms for linear inequalities
in [General Programming]
|
From: Toby on 3 Feb 2010 16:21 On Feb 3, 9:03 pm, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: > Toby <t.h...(a)liv.ac.uk> writes: > > Apologies if the solution to the following is well known, but I > > haven't managed to find anything. > > > Given k linear inequalities in n real variables, i.e. > > > a^i_1 x_1 + a^i_2 x_2 + ... + a^i_n x_n >= 0 (1 <= i <= k) > > > (where the coefficients a^i_j are integers), how can I: > > 1. decide whether they are consistent (i.e. there is a solution other > > than the zero one) > > My first thought was that this is linear programming but you would > have found that out by now so I suspect I've missed the point. > Anyway, I mention it just in case that is what you are looking for. > > > 2. more generally, write them in a canonical form (e.g., if the > > solution space is n-dimensional, then have one inequality for each > > hyperplane in its boundary) > > If your problem is LP, there is a huge literature on the subject > (about which I know almost nothing) which might address this second > question. > > -- > Ben. No, I think you're right. At any rate, one way to solve the first problem (though probably not the most efficient) would be to maximise both x_j and -x_j, for each j, subject to the given inequalities; then there's a non-zero solution to the inequalities if and only if one of these 2n maxima is positive. I also know nothing about LP, but it's time to start learning... Many thanks, Toby.
From: Christian Gollwitzer on 4 Feb 2010 04:30
Toby schrieb: > I also know nothing about LP, but it's time to start learning... Then take a look at the simplex algorithm: http://en.wikipedia.org/wiki/Simplex_algorithm Christian |