3
$\begingroup$

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:

  1. $2x_2 < x_1 + x_3$ is clearly solvable.
  2. $2x_1 < x_2 + x_3$, $2x_2 < x_1 + x_3$ is solvable by taking a sufficiently large $x_3$.
  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.

  1. 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.
  2. 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.
  3. 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.
$\endgroup$
4
  • 1
    $\begingroup$ Have a look at Fourier–Motzkin elimination, that could be done "by hand" $\endgroup$
    – J.J. Green
    Commented Mar 25, 2023 at 16:51
  • $\begingroup$ Thanks! Not sure if it'll lead anywhere (since the number of inequalities grows super-exponentially), but looks like it's worth a try. $\endgroup$
    – Dmitry
    Commented Mar 25, 2023 at 17:41
  • $\begingroup$ The formulation is a bit ambiguous: are all inequalities of the same type, or you have both types mixed? $\endgroup$
    – fedja
    Commented Mar 26, 2023 at 0:00
  • $\begingroup$ @fedja, Mixed, see the very last example $\endgroup$
    – Dmitry
    Commented Mar 26, 2023 at 1:33

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.