We present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per constraint (e.g. MAX-2-CSP and MIN-2-CSP), which gives the first exponential improvement over the trivial algorithm; more precisely, it is a constant factor improvement in the base of the runtime exponent. In the case where constraints have arbitrary weights, there is a (1+\epsilon)-approximation with roughly the same runtime, modulo polynomial factors. Our algorithm may be used to count the number of optima in MAX-2-SAT and MAX-CUT instances in O(m^3 2^{\omega n/3}) time, where \omega < 2.376 is the matrix product exponent over a ring. This is the first known algorithm solving MAX-2-SAT and MAX-CUT in provably less than c^n steps in the worst case, for some c < 2; similar new results are obtained for related problems. Our main construction may also be used to show that any improvement in the runtime exponent of either k-clique solution (even when k = 3) or matrix multiplication over GF(2) would improve the runtime exponent for solving 2-CSP optimization. As a corollary, we prove that an n^{o(k)}-time k-clique algorithm implies SNP \subseteq DTIME[2^{o(n)}], for any k(n) \in o(\sqrt{n/\log n}).