Minimum Vertex Cover (MVC)#

Code at:

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()

    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


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.