Member-only story
COMBINATORIAL OPTIMIZATION WITH D-WAVE OCEAN SDK
Solving Max-Cut Problems with D-Wave Quantum Annealing
Backstory
Imagine you’re a strategist for a Shōgun determined to weaken a network of clans across the region. While no single clan poses a threat, their web of alliances, varying in strength, could unite into a formidable opposition. Your mission is to disrupt these alliances by dividing the clans into two groups, eliminating the strongest connections to ensure they remain divided and unable to challenge the Shōgun’s rule!
The Max-Cut problem is a classic optimization problem in graph theory. Given a weighted graph, it seeks to partition vertices into two disjoint subsets to maximize the sum of the edge weights crossing between the two.
Example
We have vertices (nodes): V = {A, B, C, D} and edges with weights:
- (A, B) = 1
- (A, C) = 2
- (B, D) = 3
- (C, D) =4
We want to divide the vertices into two mutually exclusive groups to maximize the total weight of edges crossing between the two groups.
