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.
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ 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. $\endgroup$– Emil JeřábekApr 1, 2012 at 10:15
-
1$\begingroup$ 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... $\endgroup$– Igor RivinApr 1, 2012 at 15:19
-
1$\begingroup$ @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). $\endgroup$– Emil JeřábekApr 1, 2012 at 15:39
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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).
answered Apr 1, 2012 at 0:57
$\begingroup$
$\endgroup$
1
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.
answered Mar 31, 2012 at 22:20
-
1$\begingroup$ Don't mean to necromance but you mention " whether you need a solution that is exactly feasible (e.g. a solution expressed in infinite precision rational numbers.)", I can't find much literature on polynomial time algorithms for this (polynomial in # of variables, constraints and bit complexity of the underlying fractions) what would be an example of a polytime algorithm for this task? $\endgroup$ Aug 29, 2016 at 1:32