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.

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

Number Partitioning

Divide a set of numbers into two subsets with equal (or near-equal) sums.

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

Vertex Cover

Find the minimum set of vertices that covers every edge in a graph.

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

All optimization notebooks

Problem	Notebook
MaxCut	G70 benchmark
Number partitioning	quantum_number_partitioning.ipynb
Vertex cover	quantum_vertex_cover.ipynb
Graph partitioning	quantum_graph_partitioning.ipynb
Set cover	quantum_set_cover.ipynb
Job sequencing	quantum_job_sequencing.ipynb
k-Means clustering	quantum_kmeans_clustering.ipynb
Binary ILP	quantum_BILP.ipynb
Integer factorization	example_integer_factorisation.ipynb
n-Queens	QuantumnQueenProblem.ipynb
Sudoku	QuantumSudoku.ipynb
Protein folding	QuantumProteinFolding.ipynb
RNA folding	example_rna_folding.ipynb
Multi-vehicle routing	quantum_multi_vehicle_routing
Workforce scheduling	quantum_workforce_scheduling
Flow shop scheduling	quantum_flow_scheduling