Minimum Vertex Cover (MVC)#
Code at: https://github.com/qiboteam/qibo/tree/master/examples/mvc
Given an undirected graph with a set of nodes V and edges E, A vertex cover of a graph is a set of nodes that includes at least one endpoint of every edge of the graph. The Minimum Vertex Cover (MVC) problem is an optimisation problem that find smallest vertex cover of a given graph.
Load graph from csv#
import networkx as nx
import csv
import matplotlib.pyplot as plt
from mvc import qubo_mvc, qubo_mvc_penalty, mvc_feasibility, mvc_easy_fix, mvc_energy
def load_csv(filename:str):
""" Load graph from csv file
"""
with open(filename, 'r', newline='') as f:
reader = csv.reader(f)
data = [[int(row[0]), int(row[1]), float(row[2])] for row in reader]
nodes = [k0 for k0, k1, v in data if k0 == k1]
edges = [[k0, k1] for k0, k1, v in data if k0 != k1]
g = nx.Graph()
g.add_nodes_from(nodes)
g.add_edges_from(edges)
node_weights = {k0: {'weight': v} for k0, k1, v in data if k0 == k1}
edge_weights = {(k0, k1): {'weight': v} for k0, k1, v in data if k0 != k1}
nx.set_edge_attributes(g, edge_weights)
nx.set_node_attributes(g, node_weights)
return g
csv Format:
0,0,0.4696822179283675 1,1,0.6917392308135916 2,2,0.7130420958314817 3,3,0.49342677332980056 4,4,0.49661600571433673 5,5,0.55601135361347 6,6,0.2831095711244086 7,7,0.18737823232636885 0,1,0.98602725407379 1,2,0.935853268681996 2,3,0.23080434023289664 4,5,0.25521731195623476 5,6,0.37096743935296606 6,7,0.04408120693490547 0,2,0.5619060764177991 4,7,0.48402095290884917 1,6,0.7106584134580318
g = load_csv('mvc.csv')
pos = nx.spring_layout(g, seed=1234)
nx.draw(g, pos)
print(f'Number of node is {len(g.nodes)}')
print(f'Number of edge is {len(g.edges)}')
Number of node is 8
Number of edge is 9
QUBO formulation#
Estimate penalty#
penalty = qubo_mvc_penalty(g)
print(f'The penalty is {penalty}')
The penalty is 1.6548482220717595
Formulate QUBO (weighted minimum vertex cover)#
linear, quadratic = qubo_mvc(g, penalty=penalty)
print(f'Number of linear terms: {len(linear)}')
print(f'Number of quadratic terms: {len(quadratic)}\n')
Number of linear terms: 8
Number of quadratic terms: 9
Generate random solutions#
import numpy as np
rng = np.random.default_rng(seed=1234)
random_solution = {i: rng.integers(2) for i in g.nodes}
print(f'The random solution is {random_solution}\n')
The random solution is {0: 1, 1: 1, 2: 1, 3: 0, 4: 0, 5: 1, 6: 0, 7: 0}
Check feasibility#
feasibility = mvc_feasibility(g, random_solution)
print(f'The feasibility is {feasibility}\n')
The feasibility is False
Fix broken constraints#
fixed_solution = mvc_easy_fix(g, random_solution)
print(f'After fixation, the solution is {fixed_solution}\n')
After fixation, the solution is {0: 1, 1: 1, 2: 1, 3: 0, 4: 1, 5: 1, 6: 1, 7: 0}
feasibility = mvc_feasibility(g, fixed_solution)
print(f'The feasibility is {feasibility}\n')
The feasibility is True
Visualisation#
fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(12.8,4.8))
colour_b4fix = ['C1' if random_solution[n] else 'C0' for n in g.nodes]
colour_fixed = ['C1' if fixed_solution[n] else 'C0' for n in g.nodes]
nx.draw(g, pos, node_color=colour_b4fix, ax=ax0)
ax0.set_title(f'Vertex cover in orange before fix')
nx.draw(g, pos, node_color=colour_fixed, ax=ax1)
ax1.set_title(f'Vertex cover in orange after fix')
Text(0.5, 1.0, 'Vertex cover in orange after fix')
Calculate energy#
energy = mvc_energy(g, fixed_solution)
print(f'The energy is {energy}')
The energy is 3.2102004750256556
Hamiltonian of the MVC problem#
ham = hamiltonian_mvc(g, penalty=penalty, dense=True)
[Qibo 0.1.8|INFO|2022-11-01 10:26:19]: Using numpy backend on /CPU:0
Solve the hamiltonian with QAOA#
from qibo import models, hamiltonians
# Create QAOA model
qaoa = models.QAOA(ham)
# Optimize starting from a random guess for the variational parameters
initial_parameters = 0.01 * np.random.uniform(0,1,2)
best_energy, final_parameters, extra = qaoa.minimize(initial_parameters, method="BFGS")
[Qibo 0.1.8|WARNING|2022-10-31 14:14:37]: Calculating the dense form of a symbolic Hamiltonian. This operation is memory inefficient.