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?
