<p>For your first question, without the total order, the answer to your question is that it's essentially as hard as linear programming. Here's an outline of a proof.</p>

<p>First, let's establish a variable $x_1&gt;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 &lt; x_2,$$ 
$$x_1 + x_2 &lt; x_3,$$
$$x_2+x_3 &lt; x_4,$$
and so on. With a long enough chain, this will tell us that $Nx_1 &lt; x_i$, or $\epsilon &lt; 1/N$, for some very large $N$ ($N$ is a Fibonacci number, and so grows exponentially in $i$). </p>

<p>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 &lt; x_{t&#39;} &lt; x_{t&#39;&#39;} &lt; x_t + \epsilon$$ and let $x_t + x_{t&#39;} + x_{t&#39;&#39;}$ 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.</p>

<p>I don't know how to analyze the second question, asking about the case where there's a total order on all subsets. </p>

CC BY-SA 3.0
2012-05-11T19:30:22.290Z
2012-05-12T13:50:15.760Z
2012-05-12T13:50:15.760Z
Peter Shor 
<p>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 &lt; \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\}$?</p>

CC BY-SA 3.0
2012-05-05T21:06:54.120Z
Over what field are you solving these inequalities? Integers or reals?
Ankur
CC BY-SA 3.0
2012-05-05T21:12:07.183Z
Solving them over reals. It shouldn't matter whether it's over integers or reals though, right?
jonderry
CC BY-SA 3.0
2012-05-05T21:41:31.113Z
I am not sure it doesn't matter. For existence of solutions, for example, it clearly makes a difference.
Ankur
CC BY-SA 3.0
2012-05-05T21:44:18.203Z
Do you have an example?
jonderry
CC BY-SA 3.0
2012-05-06T00:54:57.400Z
I do not know what you mean by a “simple algorithm,” but the problem can be easily reduced to the usual linear programming in which the inequalities are non-strict.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-06T02:16:22.397Z
By simple algorithm, I mean something that coded in 30 minutes or so without libraries.
jonderry
CC BY-SA 3.0
2012-05-06T14:22:11.647Z
@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 
CC BY-SA 3.0
2012-05-06T16:29:34.303Z
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
CC BY-SA 3.0
2012-05-06T16:32:40.303Z
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
CC BY-SA 3.0
2012-05-06T16:41:15.513Z
@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
CC BY-SA 3.0
2012-05-06T19:20:31.170Z
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
CC BY-SA 3.0
2012-05-09T06:50:30.997Z
What is a solution supposed to look like? A single example which satisfies the inequalities, or what?
Andrej Bauer
CC BY-SA 3.0
2012-05-09T17:54:01.233Z
Yes, that would be sufficient.
jonderry
<ds.algorithms><linear-algebra><linear-programming>
Efficiently solve a system of strict linear inequalities with all coefficients equal to 1 without using a general LP solver?
jonderry
# Efficiently solve a system of strict linear inequalities with all coefficients equal to 1 without using a general LP solver?

(Asked by: username_0 on 2012-05-05)

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\}$?

**Tags:** ds.algorithms, linear-algebra, linear-programming

> **Comments:**
> **username_1**: Over what field are you solving these inequalities? Integers or reals?  
> **username_0**: Solving them over reals. It shouldn't matter whether it's over integers or reals though, right?  
> **username_1**: I am not sure it doesn't matter. For existence of solutions, for example, it clearly makes a difference.  
> **username_0**: Do you have an example?  
> **username_2**: I do not know what you mean by a “simple algorithm,” but the problem can be easily reduced to the usual linear programming in which the inequalities are non-strict.  
> **username_0**: By simple algorithm, I mean something that coded in 30 minutes or so without libraries.  
> **username_3**: @username_1: 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.  
> **username_2**: 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?  
> **username_1**: Good point Peter Shor. username_0, 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.  
> **username_0**: @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).  
> **username_2**: 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.  
> **username_4**: What is a solution supposed to look like? A single example which satisfies the inequalities, or what?  
> **username_0**: Yes, that would be sufficient.  

---

## 1 answers

### Answer by username_3 on 2012-05-11. Score: 9 | Accepted answer

For your first question, without the total order, the answer to your question is that it's essentially as hard as linear programming. Here's an outline of a proof.

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.

I don't know how to analyze the second question, asking about the case where there's a total order on all subsets.


---

