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 secion of our documentation explains how to convert between the QUBO and ising:
https://docs.dwavesys.com/docs/latest/c_gs_9.html#transformations-between-ising-and-qubo
There are also libraries to convert qubo to ising and ising 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
Hello,
There is a Weighted Max Cut function using an ising model here:
https://docs.ocean.dwavesys.com/en/stable/docs_dnx/reference/algorithms/generated/dwave_networkx.algorithms.max_cut.weighted_maximum_cut.html
You can see the source code here:
https://github.com/dwavesystems/dwave-networkx/blob/0.8.12/dwave_networkx/algorithms/max_cut.py#L88
This example is formulated using an ising model, however you can convert between ising and QUBO quite easily.
There is a library for this here:
https://docs.ocean.dwavesys.com/en/stable/docs_dimod/reference/generated/dimod.utilities.ising_to_qubo.html
Similarly, you can see the source code here:
https://github.com/dwavesystems/dimod/blob/0.12.0/dimod/utilities.py#L155
Please sign in to leave a comment.