Was that running all threads of the i7 versus all compute units of the GPU? Did you maximize the # of instances each could do with its available compute units, i.e. normalize for if the GPU has 8 or 16GB as necessary to max out its FLOPS?
That's with maxing out either cores (CPU) or memory bandwidth (GPU).
But not necessarily maxing out CPU computation, since the NP problem is memory latency bound i.e. cores spend a lot of time idle. This is why TDP isn't a reliable estimate of what is going on. I assume you know the CPU has 25 times lower/faster main memory latency than the GPU. So the CPU may be sucking a lot more electricity than the GPU which is hitting its bound on memory bandwidth (and not latency thus not maximum masked parallel computation).
I am shocked that you hadn't purchased a $20 Kill-A-Watt meter given you have invested so much of your time on this. However, I believe these may not be available in some countries in Europe. In the USA, we can order it from Amazon.
I see you said you maxed out memory bandwidth, but what about trading some memory for 10X more computation until the memory bandwidth bound and computation bound (FLOPS) are matched?
The only known trade-off uses k times less memory but 15k times more computation *and* memory accesses.
Perhaps there might be a probabilistic approach. I really haven't studied the NP problem you are applying. It worries me that you assume there aren't other tradeoffs when this is not serial random walk. Your claims are graph-theoretic only, not informational theoretic (as is the case in a perfectly uniformly distributed serial random walk). How extensively is this specific NP problem studied?