Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
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 '12 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 '12 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 '12 at 15:39
add comment

2 Answers 2

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.

share|improve this answer
add comment

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.