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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.