Algorithms for linear inequalities
in [General Programming]
|
From: Toby on 2 Feb 2010 16:12 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) 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) In the examples I'm interested in, n is typically around 10 or 20. Thanks in advance.
From: Andrew Poelstra on 3 Feb 2010 11:51 On 2010-02-02, Toby <t.hall(a)liv.ac.uk> wrote: > 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) > 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) > > In the examples I'm interested in, n is typically around 10 or 20. > For 1: How big are a_i? If they are reasonable you could probably simply do Gauss elimination and check for zero rows; otherwise you will likely need to pick up a numerics textbook, or use a prebuilt library.
From: Toby on 3 Feb 2010 15:16 On Feb 3, 4:51 pm, Andrew Poelstra <apoels...(a)localhost.localdomain> wrote: > On 2010-02-02, Toby <t.h...(a)liv.ac.uk> wrote: > > > > > 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) > > 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) > > > In the examples I'm interested in, n is typically around 10 or 20. > > For 1: > > How big are a_i? If they are reasonable you could probably simply > do Gauss elimination and check for zero rows; otherwise you will > likely need to pick up a numerics textbook, or use a prebuilt > library. Thanks for your reply. The coefficients aren't very big, but I think Gaussian elimination won't do the trick in general. I expect there to be linear dependencies between the rows, but that doesn't mean the inequalities are inconsistent - it's quite possible, though obviously a trivial case, to have the same inequality repeated several times. (Also, since they're inequalities you can only add positive multiples of one row to another, so, at least looking at it naively, Gaussian elimination isn't going to be possible.)
From: Andrew Poelstra on 3 Feb 2010 15:56 On 2010-02-03, Toby <t.hall(a)liv.ac.uk> wrote: > On Feb 3, 4:51�pm, Andrew Poelstra <apoels...(a)localhost.localdomain> > wrote: >> On 2010-02-02, Toby <t.h...(a)liv.ac.uk> wrote: >> >> >> >> > 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) >> > 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) >> >> > In the examples I'm interested in, n is typically around 10 or 20. >> >> For 1: >> >> How big are a_i? If they are reasonable you could probably simply >> do Gauss elimination and check for zero rows; otherwise you will >> likely need to pick up a numerics textbook, or use a prebuilt >> library. > > Thanks for your reply. > > The coefficients aren't very big, but I think Gaussian elimination > won't do the trick in general. > > I expect there to be linear dependencies between the rows, but that > doesn't mean > the inequalities are inconsistent - it's quite possible, though > obviously a trivial case, to have > the same inequality repeated several times. > > (Also, since they're inequalities you can only add positive multiples > of one row to another, so, > at least looking at it naively, Gaussian elimination isn't going to be > possible.) Oh! Then I am far out of my depth :). But supposing that you first use Gaussian elimination to find any actual intersections of your lines (since these may represent a valid space of size zero, which would probably trip up the following algorithm). What I would try to do is build a matrix (say, 100x100) that covers the entire grid and try to do it graphically - then zoom in on any valid-looking areas and interate until either a sizable portion of my space was valid, or it was clear that there are no valid solutions. If that didn't work out, then I would pay a visit to the local university and find somebody with too much time on his hands.
From: Ben Bacarisse on 3 Feb 2010 16:03
Toby <t.hall(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. |