For $n$ real variables $x_1, \ldots, x_n$, I have a bunch of inequalities of form $2 x_i > x_j + x_k$ or $2 x_i < x_j + x_k$, where $i,j,k$ are distinct. My goal is to determine whether this set of inequalities has a solution (the bonus question is to find a solution). It's important that inequalities are strict (otherwise, $x_1=x_2=\ldots=x_n$ is a solution).
For every instance, I can feed it to an LP-solver, and get an answer. However, I'm doing it to get an insight into a broader problem, so I'm wondering if there is a humanly-understandable way to check if a solution exists (and possibly find it). I tried to understand the simplex method for this case and didn't get any insights, but maybe it's just me.
There seems to be a relation to "non-negative vector dependence". Namely, if we write every constraint in form $c_i < 0$, and there exist $\alpha_1, \alpha_2, \ldots$ such that
- $\alpha_i$ are non-negative and not all $\alpha_i$ are $0$, and
- $\sum_i \alpha_i c_i \equiv 0$,
then no solution exists (since we can sum up the inequalities with coefficients $\alpha_i$ and get $0 < 0$).
Examples:
- $2x_2 < x_1 + x_3$ is clearly solvable.
- $2x_1 < x_2 + x_3$, $2x_2 < x_1 + x_3$ is solvable by taking a sufficiently large $x_3$.
- $2x_1 < x_2 + x_3$, $2x_2 < x_1 + x_3$, and $2x_3 < x_1 + x_2$ is not solvable: by summing these inequalities, we get $2 (x_1 + x_2 + x_3) < 2 (x_1 + x_2 + x_3)$. In this case, the inequalities are non-negatively linearly dependent.
If it somehow simplifies the problem, then a more restrictive version of the problem assumes additional constraints $x_1 < x_2 < \ldots < x_n$ (again, important that inequalities are strict). In this case, there seems to be some relation to balanced bracket sequences. Namely, assume that $+1$ corresponds to an opening bracket, and $-1$ corresponds to a closing bracket. Then there is a contradiction if we can write a balanced bracket sequence using a non-negative combination of the constraints.
Examples: consider 4 variables.
- Constraint $2x_2 > x_1 + x_3$ corresponds to a vector $(-1,2,-1,0)$, corresponding to a sequence
')' + '((' + ')' + '' = ')(()', which is not balanced, so no contradiction here. - On the other hand, constraint $2x_1 > x_2 + x_3$ corresponds to a vector $(2,-1,-1,0)$, corresponding to a sequence
'((' + ')' + ')' + ''=''(())', which is balanced, and hence there is a contradiction. - Constraint $2x_2 > x_1 + x_4$ and $2x_3 < x_1 + x_4$ correspond to vectors $(-1,2,0,-1)$ and $(1, 0, -2, 1)$. Summing these vectors, we get $(0, 2, -2, 0)$ corresponding to sequence
'' + '((' + '))' + '' = '(())', which is balanced, and hence there is a contradiction.
