I have a problem as follows. Really appreciate if anyone can give me some suggestions.
I have $4000$ binary variables $\{x_0, x_1,...x_{3999}\}$ and $4000$ inequalities which have both binary addition (denoted as $+'$) and normal (arithmetic) addition (denoted as $+$).
For example, inequality $1$:
$$ (x_0 +' x_{39} +' x_{71} +' x_{3191}) + (x_{1} +' x_{44} +' x_{182} +' x_{2142}) + ... \leq 1 $$ inequality $2$: $$ (x_3 +' x_9 +' x_{39}) + (x_{1} +' x_{90}) + ... \leq 1 $$ ... inequality $4000$: $$ (x_{99} +' x_{51} +' x_{1191}) + (x_{171} +' x_{1441} +' x_{1821} +' x_{2142}) + ... <= 1 $$
Question 1: is there any way to tell if there is no solution rather than solving it?
Question 2: if there are some solutions, how to find some of them quickly?
Thank you very much, any suggestion is highly appreciated.
It appears that your problem is a more complex version of the $3-SAT$ problem, which can be found and explained here.
As for your questions, it is unknown whether or not these types of problems can be solved efficiently (i.e. non-exponentially), however most theorize that you cannot. However if you were to find an algorithm that quickly solved the problem, there is quite the large bounty associated with it!