Efficient algorithm finding 'a' solution of system of linear inequalities - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T01:48:05Z http://mathoverflow.net/feeds/question/121536 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/121536/efficient-algorithm-finding-a-solution-of-system-of-linear-inequalities Efficient algorithm finding 'a' solution of system of linear inequalities Moon 2013-02-11T22:51:42Z 2013-02-11T23:38:29Z <p>I'm working on rational number field \$\mathbb{Q}\$.</p> <p><strong>Is there an efficient algorithm finding a solution of system of linear inequalities?</strong></p> <p>In many computer algebra systems like Sage or Maple, there are functions finding the whole solution set, but in my problem (approximately 40 dimensional vector space with 600 inequalities) it seems that the computation is too heavy. Also, in my situation I don't need the whole set - just a single solution is sufficient. What is a good method to find a solution?</p> http://mathoverflow.net/questions/121536/efficient-algorithm-finding-a-solution-of-system-of-linear-inequalities/121537#121537 Answer by Abhinav Kumar for Efficient algorithm finding 'a' solution of system of linear inequalities Abhinav Kumar 2013-02-11T23:13:09Z 2013-02-11T23:13:09Z <p>You can do linear programming (for example, by giving it a random objective function); this will return a feasible solution - in fact, a vertex of the solution set. You can run such a linear program in maple (and possibly in sage). For something faster see the exact rational LP solver at <a href="http://www2.isye.gatech.edu/~wcook/qsopt/ex/index.html" rel="nofollow">http://www2.isye.gatech.edu/~wcook/qsopt/ex/index.html</a></p> http://mathoverflow.net/questions/121536/efficient-algorithm-finding-a-solution-of-system-of-linear-inequalities/121538#121538 Answer by unknown (google) for Efficient algorithm finding 'a' solution of system of linear inequalities unknown (google) 2013-02-11T23:38:29Z 2013-02-11T23:38:29Z <p>You can use a genetic algorithm (very fast in this kind of problems) <a href="http://en.wikipedia.org/wiki/Genetic_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Genetic_algorithm</a> The possible DNA is a sequence of the binary representation of 40 float numbers. One evaluation criteria you can use is the uniform error of all inequalities. So, you will find 'a' solution of your problem if the evaluation of the best individual is zero. Of course this is the lazy method, it just works! You can try to solve this using a linear program, but i can't tell you if 600 inequalities and 40 dimensions will be solved very fast with a simple LP-solver.</p>