An Algorithm for solving linear inequalities with two variables

Question

I am trying to find an algorithm to determine existence of strictly positive integral solutions for a set of linear inequalities with two variables and the following form:

• 𝑎₁𝑥 + 𝑏₁𝑦 ≤ 𝑙₁
• 𝑎₂𝑥 + 𝑏₂𝑦 ≤ 𝑙₂
• 𝑎₃𝑥 + 𝑏₃𝑦 ≤ 𝑙₃
• ...

The problem also involves a final inequality of the following form:

• 𝑥 + 𝑦 ≥ 𝑙_𝑛

Some linear programming techniques should work here, and I am not well versed in them. I have been looking for a more adhoc solution, perhaps exploiting the nature and constraints (types of inequality) given in the problem. Any insight or algorithm would be welcome, but something deterministic and linear in terms of 𝑛, where 𝑛 is the number of inequalities, would be particularly interesting.

Additional constraint: 𝑎_𝑖, 𝑏_𝑖, 𝑙_𝑖 > 0

Answer 1

The first 𝑛−1 inequalities describe lines with a negative slope. In other words, they are of the form 𝑦=𝑚𝑥+𝑐 where 𝑚 is a negative rational number (this follows from 𝑎_𝑖, 𝑏_𝑖, 𝑙_𝑖 > 0), and they exclude the area "above" them.

The last inequality describes a line at 45° with negative slope (-1), and it excludes the area "below" it.

We could picture an example problem like this:

The white area contains the solution points. The dark area is excluded by the 𝑛−1 first constraints, the violet area is excluded by the last constraint, and the purple areas exclude solutions with a negative 𝑥 or 𝑦.

As the slopes of the orange lines are guaranteed to be negative, we can conclude that if there is no point on the last line (the dark red one with slope -1) that belongs to the solution, there is no other point either. There is no way another point could be in the solution while the points on the last (dark red) line would all be excluded.

So, we "only" need to check the integer points on the last line. In other words, we can replace the final constraint with:

      𝑥 + 𝑦 = 𝑙_𝑛

We can iterate all other constraints and see how the corresponding line's slope compares to the slope of the last line:

• If less than: the orange line is more "horizontal" than the last line. The crossing with the last line represents a lower bound for 𝑥 (and upper bound for 𝑦).
• If greater than: the orange line is more "vertical" than the last line. The crossing with the last line represents an upper bound for 𝑥 (and lower bound for 𝑦).
• If equal: the orange line is parallel to the last line. If it is above the last line (or equal to it), it can be ignored. If it is below the last line, there is no solution.

At the end of this process we have a maximum lower bound and minimum upper bound for 𝑥. If these (rational) bounds still allow for a positive integer 𝑥 solution and for which the corresponding 𝑦 would also be positive, then report a success. Otherwise there is no solution.

This algorithm has a O(𝑛) time complexity.