# Efficiently solve a system of strict linear inequalities with all coefficients equal to 1 without using a general LP solver?

Per the title, other than using a general purpose LP solver, is there an approach for solving systems of inequalities over variables $x_i, \ldots, x_k$ where inequalities have the form $\sum_{i \in I} x_i < \sum_{j \in J} x_j$? What about the special case of inequalities that form a total order over the sums of the members of the power set of $\{x_i, \ldots, x_k\}$?

• @Ankur: it doesn't matter whether it's integers or reals. If these are strict inequalities, you can round them off to rationals, and then multiply them by the least common denominator to get an integer solution. – Peter Shor May 6 '12 at 14:22
• I have no idea what you can code in 30 minutes (in which language?). If that is the criterion for “simple,” is this really a question in theoretical computer science at all? – Tsuyoshi Ito May 6 '12 at 16:29
• Good point Peter Shor. jonderry, I take my statement back. I was thinking that the combinatorial problem of satisfying these strict inequalities and the convex analytic problem of finding an interior point of a cone are qualitatively distinct. I was wrong. – Ankur May 6 '12 at 16:32
• @Tsuyoshi: It doesn't need to be trivial, but I am curious to know if this can be done from first principles without using all of the extra power of a full LP solver, especially for the special case in which we have an ordering of all of the subset-sums (note in this case that polynomial time is exponential in the number of variables). – jonderry May 6 '12 at 16:41
• Then I think that “Can this problem solved efficiently without using general algorithms for linear programming?” is a good way to formulate your question better. – Tsuyoshi Ito May 6 '12 at 19:20

First, let's establish a variable $x_1>0$, which we call $\epsilon$. Now, let's choose another variable $x_i$, which we will call $1$. We want to make sure that $$\epsilon \ll 1\, .$$ To do this, consider the inequalities $$x_1 < x_2,$$ $$x_1 + x_2 < x_3,$$ $$x_2+x_3 < x_4,$$ and so on. With a long enough chain, this will tell us that $Nx_1 < x_i$, or $\epsilon < 1/N$, for some very large $N$ ($N$ is a Fibonacci number, and so grows exponentially in $i$).
We can now manufacture a linear program with integer coefficients. If we want a coefficient of 3 on $x_t$, we add the inequalities $$x_t < x_{t'} < x_{t''} < x_t + \epsilon$$ and let $x_t + x_{t'} + x_{t''}$ stand in for 3$x_t$. If you want larger coefficients, you can get them by expressing the coefficients in binary notation, and making inequalities that guarantee that $x_u \approx 2x_t$, $x_v \approx 2x_u$, and so on. To get the right-hand-side, we do the same with the variable $x_i = 1$. This technique will let us use linear programs of the OP's form to approximately check feasibility for arbitrary linear programs with integer coefficients, a task which is essentially as hard as linear programming.