Advanced combinatorial optimization

NP-hard problems

Among all the combinatorial problems, the ones with highest practical importance and repeated appearance are NP-hard problems. Quantum annealing machines have been dedicated to tackle such problems, when represented in an Ising or QUBO form (see Combinatorial optimization). Some of them, like max cut, graph colouring, number partitioning, etc. could be easily represented in an Ising or QUBO form using myQLM tools. A description of these problems can be found below and the respective helper classes for each problem are given in the Source code.

Unconstrained Graph Problems

These problems concern graphs for which any output result is valid. In other words, any solution will obey the criteria for a right solution. However, this result may not be the most optimal.

Max cut

Given an undirected graph with vertex set \(V\) and edge set \(E\), the problem consists in partitioning the graph into two subgraphs connected by the maximum number of edges. Annealing the problem with the MaxCut class needs \(\#V\) spins (one spin per vertex of the graph).

Graph Partitioning

Given an undirected graph with vertex set \(V\) and edge set \(E\), the problem consists in partitioning the graph into two equally-sized subgraphs connected by the minimal number of edges. Annealing the problem with the GraphPartitioning class needs \(\#V\) spins (one spin for each individual vertex).

Constrained Graph Problems

A graph problem is constrained when the output solution needs to obey some conditions in order to be valid. For example, Graph Colouring requires that every two nodes connected by an edge are coloured differently - so if the solution graph does not have this property, it is not valid. Therefore, we call constrained all problems with conditional correctness of their solutions.

Graph Colouring

Given an undirected graph with vertex set \(V\) and edge set \(E\) and a a set of \(n\) colours, the problem consists in finding whether we can colour every node of the graph in one of these \(n\) colours such that no edge connects nodes of the same colour. We therefore need \(nN\) spins to anneal the problem with our GraphColouring class, where \(N\) is the number of vertices of the graph. The classical complexity of the best known approximate algorithm for this problem is \(O(N(log log N)^2 (log N)^3)\).

K-Clique

Given an undirected graph with vertex set \(V\) and edge set \(E\), the problem consists in finding out whether there exists a complete subgraph of size \(K\). Annealing the problem with the help of our KClique class requires \(\#V\) spins (one spin per vertex).

Vertex Cover

Given an undirected graph with vertex set \(V\) and edge set \(E\), the problem consists in finding the smallest number of nodes to be coloured, such that every edge has a coloured vertex. As an addition, we want to know which these vertices are. To anneal this problem we would need our VertexCover class with \(\#V\) spins (one spin per vertex).

Other problems

Some problems are more numbers-oriented, like Number Partitioning and Binary Integer Linear Programming. Both of them also belong to the class of NP and the first one can be well solved via Simulated Annealing (SA).

Number Partitioning

Given a set of real and potentially repeating numbers, the problem consists in partitioning them in two subsets, such that the sum of the numbers in both of them is equal (or as close as possible). To obtain an answer, we would need to use our NumberPartitioning class and anneal \(N\) spins, where \(N\) is the size of the set of numbers.

Binary Integer Linear Programming

Given a vector \(c\) of size \(N\), a vector \(b\) of size \(m\) and a matrix \(S\) of size \(m \times N\), the problem consists in finding a binary vector \(x\) (i.e. vector composed of 0 and 1) of size \(N\) that maximizes the dot product \(c*x\), such as \(S * x = b\).

Solving this problem using a simulated quantum annealing method requires our BILP class and \(N\) spins (one spin per binary value of \(x\)).

Simulated Quantum Annealing Benchmarking and Performance

Although Simulated Quantum Annealing (SQA) is only provided in the QLM, we present here its performance for some of the different NP problems to hint on its capabilities. Below are shown the benchmark sources, the range of spins for the problem instances, together with the average execution times.

Max Cut

For this problem, the performance we optimized was defined by \(\frac {\text{number of Max Cut edges found}} {\text{best number of Max Cut edges}}\).

  • Problem instances:

  • Spin count: from 20 to 10 000

  • Performance: > 98%

  • Execution time: mostly < 1 sec and up to 5 seconds for 10 000 spins

Graph Colouring

When optimizing this problem the performance was defined by \(\frac {\text{number of edges with vertices of different colours}} {\text{number of all edges}}\).

  • Problem instances:

    • Benchmarks: 6 - random graphs and a Leighton graph from DIMACS Graphs

    • Others: 13 random graphs

  • Spin count: from 60 to 24 000

  • Performance: 88% for best colouring, 95% - 99% for a few more colours

  • Execution time: < 10 sec for up to 24 000 spins

K-Clique

In this case, the performance we optimized was defined by \(\frac {\text{number of edges in the subgraph found}} {\text{required number of edges for the subgraph to be complete}}\).

  • Problem instances:

  • Spin count: from 450 to 4000

  • Performance: > 98%

  • Execution time: mostly < 1 sec when below 4000 spins

Vertex Cover

Here, we define the performance during optimization by \(\frac {\text{best number of coloured nodes}} {\text{found number of coloured nodes}}\).

  • Problem instances:

  • Spin count: from 450 to 4000

  • Performance: > 98%

  • Execution time: mostly < 1 sec and up to 10 seconds for 4000 spins

Number Partitioning

The performance we optimized for this problem was defined by \(\frac {\text{sum of numbers in smaller sum subset}} {\text{sum of numbers in larger sum subset}}\).

  • Problem instances: > 30 random number sets of integer or real, non-repeating or repeating numbers

  • Spin count: from 20 to 40 000

  • Performance: > 99%

  • Execution time: from instantly to 15 sec for 40 000 spins

Interfacing with DWAVE

A QUBO or Ising Instance is described by either a matrix \(Q\) or a matrix \(J\) and vector \(h\) - see Combinatorial optimization.

One can always extract from our problem classes (see NP-hard problems and the Source code) the QUBO matrix \(Q\) describing the instance, as a numpy array.

This can be fed into objects native to the DWAVE Python libraries (Dwave Ocean tools). See the following code snippet:

# import required libraries
import numpy as np
import networkx as nx
from qat.opt import VertexCover

# Specify the problem
graph = nx.Graph()
graph.add_nodes_from(np.arange(6))
graph.add_edges_from([(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 5)])

# Impose constraints for the right encoding
B = 1
A = B + 0.01

# Create problem
vertex_cover_problem = VertexCover(graph, A=A, B=B)

# Extract Q and the offset
Q, o = vertex_cover_problem.get_q_and_offset()

from dimod import BinaryQuadraticModel as BQM #  pip install dimod --user
bqm = BQM.from_numpy_matrix(Q)