Welcome to MathOverflow

Question

4

A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.

edited Apr 1 2012 at 5:27

Uday
1,151●5●14

asked Mar 31 2012 at 21:41

GB
368●1●6

2

You can compute the optimum of a linear program by using binary search on feasibility of the program together with an added linear constraint, hence feasibility testing is computationally about as complicated as full-blown linear programming. – Emil Jeřábek Apr 1 2012 at 10:15

I almost put that comment into my response, but then I started thinking about getting estimates on the biggest possible size of optimum, and decided that it is a little trickier than it looks... – Igor Rivin Apr 1 2012 at 15:19

@Igor: The optimum is attained at a vertex of the polytope defined by the program, which is a solution of a linear system consisting of a subset of the inequalities turned into equalities. As such, it is polynomially bounded (in terms of bit-length of the numerator and denominator, i.e., logarithmic height). – Emil Jeřábek Apr 1 2012 at 15:39

Brian Borchers · Answer 1 · 2012-03-31 22:20:07Z UTC

You haven't said whether you're interested in theoretical analysis or practical computation. At the practical level, you also haven't specified whether you can live with an approximate floating point solution or whether you need a solution that is exactly feasible (e.g. a solution expressed in infinite precision rational numbers.) Finally, if you are interested in doing this in practice, it would be important to know something about the size of the problem instances that you need to solve.

From the point of view of practical computation with floating point numbers on problems of reasonable size (problems with hundreds of thousands of constraints and millions of variables are often solved in practice), using a good LP solver is definitely the way to proceed- this technology has been developed to a very high level and nothing you could cook up would be faster.

From the theoretical point of view, the LP formulation is solvable in polynomial time. I don't believe that you can get any improvement in the computational complexity by solving a feasibility problem rather than the optimization version of the problem.

Igor Rivin · Answer 2 · 2012-04-01 00:57:33Z UTC

Most linear programming solvers check for feasibility first (usually this takes as much time as the second phase, which is actually finding the optimum, and uses the exact same algorithm). I would advise reading a standard textbook on the subject (Luenberger is good, Schrijver great if you are interested in integer/mixed problems).

How do you tell if a system of linear inequalities has a solution?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.