What are the prominent algorithms for solving systems of linear inequalities?

Why, you may ask?

The Python sympy symbolic library provides solutions to single, linear Diophantine equations in terms of parametric variables. For instance,

{(t_0, -9*t_0 - 5*t_1 + 154, -5*t_0 - 3*t_1 + 77)}


Without worrying about coding details, how can one solve such a system of parametric expressions for values of the original variables constrained to be, for instance, greater than zero.

Are there any opensource products?

• Sage can do this most likely, although integer linear programming is generally NP-hard. – Kirill Oct 26 '16 at 18:39
• Thank you, yes, I understand. I'm asking because I would like to offer an example involving only a small number of variables, for sympy. – Bill Bell Oct 26 '16 at 18:51
• Can you explain what the syntax of the example means? To me, this simply reads like a collection of linear expressions. How does it represent a system of linear inequalities? – Wolfgang Bangerth Oct 26 '16 at 19:51
• @WolfgangBangerth: Say the Diophantine equation were given in terms of x, y and z. Then one could make arbitrary choice of integers t_0 and t_1 and then one tuple of values for x, y and z would be given by that tuple in the set. I would like to be able to solve, for instance, for the system of inequalities where each item in the tuple is set >0. – Bill Bell Oct 26 '16 at 20:18
• So is there only one solution, or is it a whole region in space that satisfies these equations? Are you only interested in one feasible solution, or in characterizing the whole region? – Wolfgang Bangerth Oct 27 '16 at 14:02

1 Answer

If you are looking for a numerical answer, LP and MILP solvers can efficiently (not always for MIP) provide you with a feasible solution by optimizing an objective function of zeroes.