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.
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$.