Consider $J = \sum_{i=0}^{N}y_{i1}x_{i}y_{i+1}$ where $+$ and $$ in the indices are mod $N+1$. Let $x_{i} = 1  y_{i} \in \{0,1\}$. What are some of the tools useful and relaxation techniques available to maximize $J$ or any other symmetric multivariate polynomial?

For the particular polynomial, you don't need any fancy techniques, as opaquely pointed out by @Noah Stein: you write $J=\sum_{i=0}^n y_{i1}y_i y_{i+1} + \sum_{i=0}^n y_{i1}y_{i+1}.$ Both the first and the second sums depend fairly simply on the pattern of runs of $1$s and $0$s in your sequence $y_0, \dotsc, y_n$  I leave it to you to work out the details, which are not too hard. In general, you are trying to maximize a sum of boolean monomials, and that is both a hard and and oftenarising problem. One relaxation is to replace your variables $y_i$ by $z_i^\alpha,$ where $z_i$ are continuous in [0, 1], and $\alpha$ is a positive real number. As $\alpha$ goes to infinity, the problem becomes discrete, and one can try simulated annealing to deal with the continuous problem  there are no general techniques, since the function is generally not convex, so you have to slaughter many goats and hope for the best (nonetheless, I am ashamed to admit that many centuries ago I was one of the inventors on a patent based on the above idea for the purpose of VLSI testing). 


The optimization is a summation of triples over a cycle. You can enumerate the value of a few binary variables to break the cycle down to a (secondorder) Markov chain. Then dynamic programming can be used to solve this problem efficiently. To elaborate, consider enumerating $x_0$ and $x_N$, which are both binary variables. Then the cycle becomes a chain in which the first term contains only $x_1$ (since $x_0$ and $x_N$ are known), the second term contains only $x_1$ and $x_2$ ($x_0$ is known), and similarly for the last two terms. The rest terms still contain three x's. Then if we consider state $s_i = [x_i, x_{i+1}]$ (which has four possible choices), then the term $x_{i1}y_ix_{i+1}$ can be written in $\phi_i(s_{i1}, s_i)$ and the entire summation can be written as $J = \sum_{i=2}^{N2} \phi_i(s_{i1}, s_{i})$ which can be solved efficiently by dynamic programming. 

