Solving weighted MaxCut with QUBO
Hello together!
I would like to solve the MaxCut problem for a weighted graph.
For this I already use the functions from https://docs.ocean.dwavesys.com/projects/dwave-networkx/en/latest/reference/algorithms/max_cut.html.
However, these use the Ising Model in the background and partially do not provide me with the optimal solutions.
Now I would like to solve the problem with the QUBO model.
For this I currently use the approach of: https://github.com/dwave-examples/maximum-cut.
My problem is that I do not know how to create a QUBO for a weighted graph.
It would be great if someone has some advice or hint for me.
Thanks a lot!
Comments
Hello,
It might help to better understand the problem formulation and work directly with the QUBO, however all problems run on the QPU as an ising problem, and QUBO and ising can be converted from one to the other.
This document explains the equivalence between QUBO and ising, how to convert between the two, and how QUBO problems are formulated:
https://www.dwavesys.com/sites/default/files/Guide_Prob_Form-2.pdf
This function can produce a QUBO from a BQM created using an ising model:
https://docs.ocean.dwavesys.com/en/stable/docs_dimod/reference/generated/dimod.bqm.adjarraybqm.AdjArrayBQM.to_qubo.html#dimod.bqm.adjarraybqm.AdjArrayBQM.to_qubo
You can actually see the formulation of the QUBO in the example you mentioned above:
https://github.com/dwave-examples/maximum-cut/blob/master/maximum_cut.py
You might also want to take a look at some tips on improving results here:
https://support.dwavesys.com/hc/en-us/community/posts/360038288373/comments/360009947634
Here:
https://support.dwavesys.com/hc/en-us/community/posts/360043592114/comments/360011062194
And here:
https://support.dwavesys.com/hc/en-us/community/posts/360029357534/comments/360004903154
Please sign in to leave a comment.