NP-hard problems
Among all the combinatorial problems, the ones with highest practical importance and repeated appearance are the NP-hard problems. Real quantum annealers have been dedicated to tackle such problems, when represented in an Ising or QUBO form (refer to Annealing programming and this notebook). Some of them, like Max Cut, Vertex Cover, Number Partitioning, etc. could be easily formulated in these ways using myQLM tools. A description of these problems can be found below and the respective helper classes for each problem are given in the API. An example notebook for each problem could be found in the overview.
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.
Constrained Graph Problems
A graph problem is constrained when the output solution needs to obey some conditions in order to be valid. For example, Vertex Cover requires that every edge is connected by at least one coloured node - so if the solution graph does not have this property, it is not valid. Therefore, we call constrained all problems with conditional correctness on their solution.
Other problems
Some problems are more numbers-oriented, like Number Partitioning, which also belongs to NP-hard and can be well solved via Simulated Annealing (SA).
To solve each of the combinatorial problems with Simulated Annealing (SA) we need to feed the
solver in SimulatedAnnealing with parameters tailored for the specific problem. We provide initial parameters derived
from the target problem that can be then further fine-tuned. They can be accessed from the get_sa_initial_parameters method of
the respective problem class.