# 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:

Benchmarks: 9 planar and random graphs from the Gset benchmark dataset

Others: > 20 random trees

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:

Benchmarks: 27 differently generated graphs from the BHOSLIB, DIMACS and Clique benchmark datasets

Others: 5 random graphs

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:

Benchmarks: 21 random graphs from the BHOSLIB and OEIS benchmark datasets

Others: 5 random graphs

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