0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ Commented Sep 13, 2021 at 14:36
  • $\begingroup$ I have edited my question. $\endgroup$
    – mkultra
    Commented Sep 13, 2021 at 14:58
  • $\begingroup$ Try using an integer programming solver. $\endgroup$ Commented Sep 13, 2021 at 15:01

2 Answers 2

2
$\begingroup$

You should add all inequalities and exclude all the terms that repeat on both sides. The result is:

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .