> ## Documentation Index > Fetch the complete documentation index at: https://dynex.mintlify.app/llms.txt > Use this file to discover all available pages before exploring further. # Optimization Algorithms > MaxCut, graph partitioning, job sequencing, and combinatorial problems on Dynex # Optimization Algorithms Dynex excels at NP-hard combinatorial optimization problems. All examples use the annealing interface (BQM/QUBO formulations). ## MaxCut Partition graph vertices into two sets to maximize the number of edges between sets. ```python theme={null} import dynex import dimod import networkx as nx from dynex import DynexConfig, ComputeBackend # Build a random graph G = nx.gnp_random_graph(20, 0.4, seed=42) # MaxCut QUBO: maximize sum of (1 - x_i*x_j) for each edge (i,j) # Equivalent: minimize sum of x_i*x_j - constant Q = {} for i, j in G.edges(): Q[(i, i)] = Q.get((i, i), 0) - 1 Q[(j, j)] = Q.get((j, j), 0) - 1 Q[(i, j)] = Q.get((i, j), 0) + 2 bqm = dimod.BinaryQuadraticModel.from_qubo(Q) model = dynex.BQM(bqm) config = DynexConfig(compute_backend=ComputeBackend.GPU) sampler = dynex.DynexSampler(model, config=config) sampleset = sampler.sample(num_reads=1000, annealing_time=200) best = sampleset.first.sample partition_0 = [v for v, val in best.items() if val == 0] partition_1 = [v for v, val in best.items() if val == 1] cut_edges = [(u, v) for u, v in G.edges() if best[u] != best[v]] print(f"Cut size: {len(cut_edges)}") ``` [G70 MaxCut benchmark notebook](https://github.com/Dynex-Development/awesome-dynex/blob/main/benchmarks/G70_dynex.ipynb) ## Number Partitioning Divide a set of numbers into two subsets with equal (or near-equal) sums. ```python theme={null} import dynex import dimod from dynex import DynexConfig, ComputeBackend numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] n = len(numbers) # QUBO: minimize (sum_i s_i * n_i)^2 where s_i in {-1, +1} # Binary encoding: x_i = (s_i + 1) / 2 -> s_i = 2*x_i - 1 Q = {} for i in range(n): for j in range(n): Q[(i, j)] = Q.get((i, j), 0) + numbers[i] * numbers[j] bqm = dimod.BinaryQuadraticModel.from_qubo(Q) model = dynex.BQM(bqm) config = DynexConfig(compute_backend=ComputeBackend.GPU) sampler = dynex.DynexSampler(model, config=config) sampleset = sampler.sample(num_reads=500, annealing_time=100) assignment = sampleset.first.sample set_a = [numbers[i] for i, v in assignment.items() if v == 0] set_b = [numbers[i] for i, v in assignment.items() if v == 1] print(f"Set A: {set_a} (sum={sum(set_a)})") print(f"Set B: {set_b} (sum={sum(set_b)})") ``` [Number partitioning notebook](https://github.com/Dynex-Development/awesome-dynex/blob/main/optimization/quantum_number_partitioning.ipynb) ## Vertex Cover Find the minimum set of vertices that covers every edge in a graph. ```python theme={null} import dynex, dimod, networkx as nx from dynex import DynexConfig, ComputeBackend G = nx.petersen_graph() penalty = 10.0 # Constraint penalty weight Q = {} # Objective: minimize number of selected vertices for v in G.nodes(): Q[(v, v)] = Q.get((v, v), 0) + 1 # Constraint: for each edge, at least one endpoint must be in cover for u, v in G.edges(): Q[(u, u)] = Q.get((u, u), 0) - penalty Q[(v, v)] = Q.get((v, v), 0) - penalty Q[(u, v)] = Q.get((u, v), 0) + penalty bqm = dimod.BinaryQuadraticModel.from_qubo(Q) model = dynex.BQM(bqm) config = DynexConfig(compute_backend=ComputeBackend.GPU) sampler = dynex.DynexSampler(model, config=config) sampleset = sampler.sample(num_reads=1000, annealing_time=200) cover = [v for v, val in sampleset.first.sample.items() if val == 1] print(f"Vertex cover: {cover} (size={len(cover)})") ``` [Vertex cover notebook](https://github.com/Dynex-Development/awesome-dynex/blob/main/optimization/quantum_vertex_cover.ipynb) ## All optimization notebooks | Problem | Notebook | | --------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------- | | MaxCut | [G70 benchmark](https://github.com/Dynex-Development/awesome-dynex/blob/main/benchmarks/G70_dynex.ipynb) | | Number partitioning | [quantum\_number\_partitioning.ipynb](https://github.com/Dynex-Development/awesome-dynex/blob/main/optimization/quantum_number_partitioning.ipynb) | | Vertex cover | [quantum\_vertex\_cover.ipynb](https://github.com/Dynex-Development/awesome-dynex/blob/main/optimization/quantum_vertex_cover.ipynb) | | Graph partitioning | [quantum\_graph\_partitioning.ipynb](https://github.com/Dynex-Development/awesome-dynex/blob/main/optimization/quantum_graph_partitioning.ipynb) | | Set cover | [quantum\_set\_cover.ipynb](https://github.com/Dynex-Development/awesome-dynex/blob/main/optimization/quantum_set_cover.ipynb) | | Job sequencing | [quantum\_job\_sequencing.ipynb](https://github.com/Dynex-Development/awesome-dynex/blob/main/optimization/quantum_job_sequencing.ipynb) | | k-Means clustering | [quantum\_kmeans\_clustering.ipynb](https://github.com/Dynex-Development/awesome-dynex/blob/main/optimization/quantum_kmeans_clustering.ipynb) | | Binary ILP | [quantum\_BILP.ipynb](https://github.com/Dynex-Development/awesome-dynex/blob/main/optimization/quantum_BILP.ipynb) | | Integer factorization | [example\_integer\_factorisation.ipynb](https://github.com/Dynex-Development/awesome-dynex/blob/main/misc/example_integer_factorisation.ipynb) | | n-Queens | [QuantumnQueenProblem.ipynb](https://github.com/Dynex-Development/awesome-dynex/blob/main/advanced_applications/QuantumnQueenProblem.ipynb) | | Sudoku | [QuantumSudoku.ipynb](https://github.com/Dynex-Development/awesome-dynex/blob/main/advanced_applications/QuantumSudoku.ipynb) | | Protein folding | [QuantumProteinFolding.ipynb](https://github.com/Dynex-Development/awesome-dynex/blob/main/advanced_applications/QuantumProteinFolding.ipynb) | | RNA folding | [example\_rna\_folding.ipynb](https://github.com/Dynex-Development/awesome-dynex/blob/main/misc/example_rna_folding.ipynb) | | Multi-vehicle routing | [quantum\_multi\_vehicle\_routing](https://github.com/dynexcoin/quantum_multi_vehicle_routing) | | Workforce scheduling | [quantum\_workforce\_scheduling](https://github.com/dynexcoin/quantum_workforce_scheduling) | | Flow shop scheduling | [quantum\_flow\_scheduling](https://github.com/dynexcoin/quantum_flow_scheduling) |