Finding a binary vector that satisfies non-linear constraints

Question

I’m looking for good heuristics for finding at least one (of a probably large set, although possibly none) high dimensional ($|v|>5000$) binary vector that satisfies a set of non-linear/non-differentiable constraints. They are of the form

$a_{i,0}<C_{i}(v)<a_{i,1}$

The functions $C_i$ will probably change not too much if any one bit is flipped (or there may be “critical” bits, but very few). The number of constraints is 5.

While the set of vectors is probably large it’s hard to find one by random search (given that number of vectors is $2^{5000}$). It’s easy to find (randomly) a vector that satisfies a few of the constraints (I think I saw 4 but 5th was very bad).

I am free to relax the constraints if it makes the problem easier (for example if the vector doesn’t exist or is extremely rare). How do I choose which $a$ to increase/decrease? My constraints are real-life task derived so I would like to not relax them if possible.

Edit: I've made a further reformulation of the question

The binary vector $v$ can be thought of as a coloring problem for graph (,,).

Each $U$ vertex is connected to 1-5 $V$ vertices, while each $V$ vertex is connected to 1-50 $U$ vertices. There are ~5k $U$ vertices and ~500 $V$ vertices. The graph may have small disconnected subgraphs, but they represent a small part of the total graph.

I am interested in binary coloring {-1, 1} of both the vertices and the edges of the graph. The constraints for the coloring are the following:

1. If edge $E_{ij}=1$ then $U_i = 1$ and $V_j = 1$
2. 80% of edges $E_{ij}=1$, the rest are -1
3. If $E_{ij}=-1$ then there is 50% chance $U_i = 1$, and independently 50% chance of $V_j = 1$
4. Stretch goal: I'd like the coloring of to be independent of how many edges it is connected to (so popular/rare $V$'s are all equally likely to be 1 or −1).