The problem of exact maximum-likelihood decoding of general linear codes is well-known to be NP-hard. If we do not require our algorithm to always give us a codeword it is possible to develop a decoder using linear programming. In the particular case of the cycle code of a graph G, we can even understand the non-codeword outputs of the linear programming decoder. These pseudo-codewords are the vector representations of cycles in the all-negative signed graph -G.