# Does this system of inequalities have a solution?

Consider the following system of inequalities:

$$\left\{ \begin{array}{ll} x_{ab}+x_{ac}+x_{ad}+x_{abc}+x_{abd}+x_{acd}+x_{abcd}\ge 4+x_{bc} +x_{bd}+x_{cd}+x_{bcd}\\ x_{ab}+x_{bc}+x_{bd}+x_{abc}+x_{abd}+x_{bcd} +x_{abcd}\ge 4+ x_{ac}+x_{cd}+x_{ad}+x_{acd}\\ x_{ac}+x_{bc}+x_{cd}+x_{abc}+x_{acd}+x_{bcd} +x_{abcd} \ge 4 +x_{ab}+x_{ad}+x_{bd} + x_{abd}\\ x_{ad}+x_{bd}+x_{cd}+x_{abd}+x_{acd}+x_{bcd}+x_{abcd} \ge 4+ x_{ab}+x_{ac}+x_{bc} +x_{abc} \end{array} \right.$$

where each $$x \in \{ 0, 1 \}$$. Does this system of inequalities have a solution?

I suspect that it doesn't have any solution. However i would like to have a proof of it.

I have a one extra question. How could i solve a similar problems? (the system of inequalities, where each variable has two possible values: $$0$$, $$1$$) Are there some common techniques, that verify whether such system is solvable?

I have heard about simplex method. Is it useful in this case?

Thank you for help.

• As the inequalities are written every variable appears on one side or the other of every one of the inequalities except for $\ x_{abc}\$, which doesn't appear on either side of the last inequality, and the variable $\ x_{bcd}\$ appears on $both$ sides of that last inequality. Should the one of those occurrences of $\ x_{bcd}\$ be $\ x_{abc}\$ instead? If you add all the inequalities up as written, you get that $\ 3x_{abc}+2x_{acd}+4x_{abcd}\ge16 \$, which is impossible if all variables have to be $0$ or $1$. Sep 13, 2021 at 14:36
• I have edited my question. Sep 13, 2021 at 14:58
• Try using an integer programming solver. Sep 13, 2021 at 15:01

$$2 x_{bcd}+2x_{acd}+2x_{abd}+4x_{abcd}+2x_{abc}\geq 16$$
But if all the $$x$$'s are 0 or 1 left-hand side is not greater than 12.
If you transfer all the variables on the left side of each inequality, you get four inequalities of the form $$c_{iab}x_{ab}+c_{iac}x_{ac}+c_{iad}x_{ad}+c_{ibc}x_{bc}+c_{ibd}x_{bd}+c_{icd}x_{cd}+c_{iabc}x_{abc}+c_{iabd}x_{abd}+c_{iacd}x_{acd}+c_{ibcd}x_{bcd}+c_{iabcd}x_{abcd}\ge4\ ,$$ where the coefficients $$\ c_{iwx}, c_{iwxy},c_{iwxyz}\$$ are as listed in the following table $$\begin{array}{c|ccccccccc} i&x_{ab}&x_{ac}&x_{ad}&x_{bc}&x_{bd}&x_{cd}&x_{abc}&x_{abd}&x_{acd}&x_{bcd}&x_{abcd}\\ \hline 1&1&1&1&-1&-1&-1&1&1&1&-1&1\\ 2&1&-1&-1&1&1&-1&1&1&-1&1&1\\ 3&-1&1&-1&1&-1&1&1&-1&1&1&1\\ 4&-1&-1&1&-1&1&1&-1&1&1&1&1\\ \hline \text{sum}&0&0&0&0&0&0&2&2&2&2&4 \end{array}$$ Summing all the inequalities tells you that they can only be satisfied if $$2x_{abc}+2x_{abd}+2x_{acd}+2x_{bcd}+4x_{abcd}\ge16\ .$$ But this is impossible if the variables are required to have values $$0$$ or $$1$$ because the value of the expression on the right can be at most $$12$$.