Checking Feasibility of Linear Program in Polynomial Time

Problem Detail: 

Given a linear system of the form:

$$\begin{array}{c} x_r = a \quad x_j = b \\ c_1x_1 + c_2x_2 + \ldots + c_nx_n = N \\ x_1+x_2 + x_3 + \ldots + x_n = k\\ 0 \le a,b,x_1,x_2,x_3...x_n \le 1\\ k \ge 0 \end{array}$$

How quickly can the feasibility of the system be checked? To clarify: $x_r,x_j$ are members of $x_1,x_2...x_n$. Would it be $O(n^{3.5})$ since I believe that is the general complexity for running a linear program or would it be less? Can one use gaussian elimination to quickly reduce the first 4 equations in $O(n^3)$ and after that systematically move through the equations starting from the terms with largest coefficient and moving to terms with smallest coefficient assigning values that bring the equations as close to satisfactory as possible?

Additional info:

I am assuming that the number of variables scales linearly. $n \ne N$ (I think that was clear though).

Asked By : frogeyedpeas

Answered By : D.W.

Restating the problem. As far as I can tell, your system is equivalent to the following:

$$c_1 x_1 + \dots + c_n x_n = N$$

subject to the constraints

$$0 \le x_1, \dots, x_n \le 1.$$

Solving this problem. This is a linear program, so certainly we can tell in polynomial time whether it has any feasible solution, as a result of the fact that there are polynomial-time algorithms for linear programming.

However, there's a better solution. We can directly solve this problem by inspection, without needing a linear programming solver.

Suppose without loss of generality that $c_1,\dots,c_j$ are positive and $c_{j+1},\dots,c_n$ are zero or negative. (You can re-order the variables to put things into this standard form.)

Then it follows that $c_1 x_1 + \dots + c_n x_n \le c_1 + \dots + c_j$. So, if $c_1 + \dots + c_j < N$, then this problem has no feasible solution. On the other hand, if $N \le c_1 + \dots + c_j$, then it is easy to demonstrate that this problem does have a solution: simply let $x_1 = \cdots = x_j = N/(c_1 + \dots + c_j)$ and let $x_{j+1} = \cdots = x_n = 0$. These $x_i$'s will all fall in the desired range.

Thus, feasibility can be checked in $O(n)$ time (in the RAM model, where basic operations take $O(1)$ time).

---

Details. Why is it fair game to reduce the problem to the form given above? How did I get the simpler form above?

Well, first off, I removed the variables $a,b$ from the linear program. No matter what values you assign to the $x$'s, you'll always be able to assign a value to $a,b$ derived from the $x$'s that satisfies the equations that mention $a,b$.

Similarly, I removed the equation $k=\dots$ and the variable, since no matter what value we assign to the other variables, we can simply set $k=x_1+\dots+x_n$ and get a value that will satisfy this equation; it will also satisfy $k\ge 0$, since all the $x_i$'s are required to be $\ge 0$. That leaves me with the problem shown at the top of my answer.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13370