Bachelorarbeit Ergebnisse reproduzieren

git clone --recursive http://sargas.org:3000/QA_SAT/BA_Reproduzierbarkeit_Anleitung.git

Setup

Zuerst muss ein virtual environment für Python eingerichtet werden. Gehen Sie hierfür in das Hauptverzeichnis des Projekts und führen Sie

pipenv install

aus. Anschließend muss noch ein kernel für jupyter erstellt werden, hierzu führen Sie

python -m ipykernel install --user --name=BA_Reproduzierbarkeit_Anleitung

aus. Anschließend kann das virtual environment mit

pipenv shell

aktiviert werden.

Kompilieren

Führen Sie folgende Anweisungen aus, um die notwendigen libraries und Tools zu kompilieren.

./qubo_lab/SconsLocal/scons.py -C ./qubo_lab/ --init

./qubo_lab/SconsLocal/scons.py -C ./qubo_lab/

Datenbanken einrichten

Es werden zwei Datenbanken benötigt, eine MySQL und eine MongoDB Datenbank. In der MongoDB Datenbank werden Objekte wie SAT-Instanzen, QUBOS oder D-Wave SampleSets gespeichert. Die MySQL Datenbank wird dazu verwendet, um Daten aus diesen Objekten zu extrahieren und diese anschließend zu untersuchen. Damit die Datenbanken genutzt werden können muss im Hauptverzeichnis ein File namens database.config angelegt werden, welches folgende Struktur aufzuweisen hat.

[INSTANCE_POOL]
user = ...
pw = ...
url = ...
port = ...
database = ...

[EXPERIMENT_DB]
user = ...
pw = ...
url = ...
port = ...
database = ...

Bei [INSTANCE_POOL] handelt es sich um die MongoDB Datenbank und bei [EXPERIMENT_DB] um die MySQL Datenbank.

Verbindung zum D-Wave Solver

Der Zugriff auf einen D-Wave Solver setzt ein dwave.config file im Hauptverzeichnis voraus. Weitere Informationen hierzu finden Sie in der offiziellen Dokumentation des D-Wave Cloud Clients :

Datensatz generieren

Ein k-SAT-Instanzen Datensatz mit einer fixer Klauselanzahl und logistisch verteilen Variablenanzahlen kann mit folgendem Python script erzeugt werden.

from qubo_lab.util import script
from qubo_lab.util import random_instance_pool as rip

instance_db = script.connect_to_instance_pool()
experiment_db = script.connect_to_experimetns_db()

script.create_experiment_scope(instance_db, "my description", "scope_name")

logistic_variable_distr_params = 
	{
	number_of_clauses: 42,
	min_variables: 5,
	max_variables: 84,
	alpha_point_of_interest: 4.2,
	steepness: 1.4
	}
	
number_of_instances = 250

instance_params = rip.Instance_parameters(42, 5, 3);

pool = rip.create_random_logistic_pool(logistic_variable_distr_params, 250, instance_params)

for instance in pool:
	instacne_id = script.write_instance_to_pool_db(instance_db, instance)
	script.add_instance_to_experiment_scope(instance_db, "scope_name", instacne_id)

Daten über k-SAT-Instanzen extrahieren

Für die spätere Analyse werden Daten über die k-SAT-Instanzen extrahiert und in einer Tabelle der MySQL Datenbank gespeichert.

Legen Sie hierfür folgende Tabelle an.

CREATE TABLE `instances` (
  `instance_id` char(24) NOT NULL DEFAULT '',
  `number_of_clauses` int(11) DEFAULT NULL,
  `number_of_variables` int(11) DEFAULT NULL,
  PRIMARY KEY (`instance_id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

Anschließend können Sie mit diesem Python code extrahiert werden.

from qubo_lab.util import script

instance_db = script.connect_to_instance_pool()

script.extract_instance_parameters()

Sie werden nun nach einigen Dingen gefragt, folgende Tabelle erklärt die Bedeutungen der Abfragen:

Abfrage	Erklärung
scope:	Name des Experiment-Scopes (scope_name)
table name:	Name der gerade erstellten Tabelle ("instances")

Minisat ausführen

Als nächstes muss der Minisat Solver auf dem gerade generierten Datensatz gelaufen lassen werden. Hierzu führen Sie vom Hauptverzeichnis

./qubo_lab/build/release/runMinisat

aus. Wenn Sie nach dem Datenbanken Konfigurationsfile gefragt werden, geben Sie das oben beschriebene database.config file an. Als "Experiment scope" geben Sie den scope_name aus dem Abschnitt "Datensatz generieren" an. Anschließend müssen die Ergebnisse des Minisat Solvers extrahiert werden. Hierfür muss eine Tabelle in der Experiment Datenbank angelegt werden:

CREATE TABLE `minisat_runs` (
  `run_id` char(24) NOT NULL DEFAULT '',
  `instance_id` char(24) DEFAULT NULL,
  `satisfiable` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`run_id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

Ist diese Tabelle angelegt, können die Ergebnisse extrahiert werden, führen Sie hierzu folgenden Python code aus.

from qubo_lab.util import data_extraction

data_extraction.extract_minisat_results()

Sie werden nun nach einigen dingen gefragt, folgende Tabelle erklärt die Bedeutungen der Abfragen:

Abfrage	Erklärung
scope:	Name des Experiment-Scopes (scope_name)
table name:	Name der gerade erstellten Tabelle ("minisat_runs")

SAT < WMIS Reduktion

Zuerst müssen die QUBOs dieser Reduktion erstellt und in der MongoDB Datenbank abgespeichert werden, was durch folgenden Python code erledigt wird.

from qubo_lab.util import script

instance_db = script.connect_to_instance_pool()

script.create_wmis_qubos_for_scope(instance_db, "scope_name")

Im nächsten Schritt müssen die erzeugten QUBOs auf dem Hardwaregraphen des D-Wave Solvers eingebettet werden.

from qubo_lab.util import script
from qubo_lab.util import queries
from qubo_lab.util import graph
from dwave.system.samplers import DWaveSampler

instance_db = script.connect_to_instance_pool()

solver_graph = graph.create_qpu_solver_nxgraph(DWaveSampler().solver)

qubos = queries.Qubo_scope_query(instance_db, "wmis_qubos")
qubos.query("scope_name")

script.find_embeddings_for_scope(instance_db, solver_graph, qubos)

Führen Sie (find_embeddings_for_scope(...)) solange aus bis alle für alle QUBOs ein Embedding gefunden wurde. Sollte dies nicht möglich sein, sind die QUBOs zu groß für den Hardwaregraphen. Nun können die QUBOs dem D-Wave Solver übergeben werden. Führen Sie hierzu

./qubo_lab/run_sampler_on_scope.py

aus. Folgende Tabelle erklärt wieder die Abfragen des Scripts:

Abfrage	Erklärung
choose mode:	wählen Sie hier qpu um den D-Wave Solver auszuwählen
ising/qubo collection:	die collection in der die QUBOs gespeichert sind ("wmis_qubos")
scope:	der oben angelegte Experiment-Scope ("scope_name")
annealing time (in us):	die Annealzeit des D-Wave Solvers pro Sample
number of reads per instance:	die Anzahl der Sample pro Instanz
qubo_negation:	wählen Sie hier false - die QUBOs müssen nicht negiert werden
save as run (numbered):	die Nummer des Durchlaufs

Nachdem der D-Wave Sovler alle Instanzen bearbeitet hat, muss zunächst wieder eine Tabelle erstellt werden,

CREATE TABLE `wmis_qpu_results` (
  `result_id` char(24) NOT NULL DEFAULT '',
  `run` int(11) DEFAULT NULL,
  `instance_id` char(24) DEFAULT NULL,
  `number_of_found_assignments` int(11) DEFAULT NULL,
  `chain_break_fraction` float DEFAULT NULL,
  `num_occurrences` int(11) DEFAULT NULL,
  `energy` float DEFAULT NULL,
  `satisfiable` tinyint(1) DEFAULT NULL,
  `anneal_time` int(11) DEFAULT NULL,
  `energy_reach` int(11) DEFAULT NULL,
  `sample_size` int(11) DEFAULT NULL,
  PRIMARY KEY (`result_id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

um anschließend Daten aus den Ergebnissen des D-Wave Solvers zu extrahieren:

from qubo_lab.util import script

instance_db = script.connect_to_instance_pool()

script.extract_wmis_qpu_results()

Abfrage	Erklärung
scope:	Name des Experiment-Scopes (scope_name)
result collection:	"wmis_qubos"
table name:	Name der gerade erstellten Tabelle ("wmis_qpu_results")

Variablenhauptstrang Methode

Zuerst müssen wieder die QUBOs der Variablenhauptstrang Methode erstellt werden.

from qubo_lab.util import script

instance_db = script.connect_to_instance_pool()

script.create_wmis_2_qubos_for_scope(instance_db, "scope_name")

Anschließend müssen wieder die Embeddings gefunden werden.

from qubo_lab.util import script
from qubo_lab.util import queries
from qubo_lab.util import graph
from dwave.system.samplers import DWaveSampler

instance_db = script.connect_to_instance_pool()

solver_graph = graph.create_qpu_solver_nxgraph(DWaveSampler().solver)

qubos = queries.Ising_scope_query(instance_db, "wmis_2_qubos")
qubos.query("scope_name")

script.find_embeddings_for_scope(instance_db, solver_graph, qubos)

Nun können Sie wieder den D-Wave Sampler über die Instanzen laufen lassen.

./qubo_lab/run_sampler_on_scope.py

Achten Sie darauf bei der Abfrage der "Ising/qubo collection" diesmal "wmis_2_qubos" anzugeben.

Nun erstellen Sie erneut eine Tabelle für die zu extrahierenden Daten.

CREATE TABLE `wmis_2_qpu_results` (
  `result_id` char(24) NOT NULL DEFAULT '',
  `run` int(11) DEFAULT NULL,
  `instance_id` char(24) DEFAULT NULL,
  `number_of_found_assignments` int(11) DEFAULT NULL,
  `chain_break_fraction` float DEFAULT NULL,
  `num_occurrences` int(11) DEFAULT NULL,
  `energy` float DEFAULT NULL,
  `satisfiable` tinyint(1) DEFAULT NULL,
  `anneal_time` int(11) DEFAULT NULL,
  `energy_reach` int(11) DEFAULT NULL,
  `sample_size` int(11) DEFAULT NULL,
  PRIMARY KEY (`result_id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

Ist die Tabelle erstellt können die Daten extrahiert werden.

from qubo_lab.util import script

instance_db = script.connect_to_instance_pool()

script.extract_wmis_2_qpu_results()

Abfrage	Erklärung
scope:	Name des Experiment-Scopes (scope_name)
result collection:	"wmis_qubos"
table name:	Name der gerade erstellten Tabelle ("wmis_2_qpu_results")

Auswertung

Die extrahierten Daten befinden sich nun in zur Auswertung geeigneter Form in der MySQL Datenbank. Für weitere Erläuterungen zur Auswertung wird auf die Bachelorarbeit verwiesen.