# Optimum Solution calculation for QAOA

In QAOA, for the MaxCut problem, one tries to find a good ratio, as close to 1 as possible, of $$\epsilon = \frac{C_{approx}}{C_{opt}}$$, where $$C_{approx}$$ is the approximate value of the cost function for some configuration of spins and $$C_{opt}$$ is the optimum cost value for the given graph. I want to calculate $$\epsilon$$ for some random instances of the MaxCut problem (with small number of vertices) and test how good the algorithm behaves.

In order to do that though, I need the exact solution of a given instance. I was wondering what is the best way to calculate it? Do a brute force in the whole configuration space? Finally, is there any Python library that will help me with my problem of obtaining the optimum solution, given the graph?