Belief propagation for approximate real 3LIN?
In coding theory, Belief Propagation is heavily used as a good heuristic for decoding (either explicit or randomly generated) LDPC codes in various settings (e.g., for the erasure channel, you want to satisfy all constraints more quickly than Gaussian elimination. For noisy channels, you want to find the "best fit", etc). I think techniques used there are directly relevant to your question. You may want to have a look at the book "Modern Coding Theory" by Urbanke and Richardson for an extensive discussion.