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 (second-order) 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_{i-1}y_ix_{i+1}$ can be written in $\phi_i(s_{i-1}, s_i)$ and the entire summation can be written as 

$J = \sum_{i=2}^{N-2} \phi_i(s_{i-1}, s_{i})$

which can be solved efficiently by dynamic programming.