# Reproducing Experiments
Before running experiments, please follow all installation instructions in the [README](README.md).
All experiments rely on first having preprocessed data. See [preprocessing](#preprocessing) for
instructions on how to preprocess the experiment dataset.
## Data (Quantum and Synthetic)
To prepare the data, run the following commands:
```
make data
python -m experiments.data.sanitize
python -m experiments.data.generate_synthetic -seeds 15
python -m experiments.data.validate -precomputed synthetic_precomputed_0-14.csv
```
Original datasets from Huffner/Wernicke, Beasley, and GKA are automatically downloaded using the `data` target of the Makefile; these are available in the `data/original/` directory.
These datasets are then sanitized with
```
python -m experiments.data.sanitize
```
which will generate a `data/converted/` directory with sanitized graph data in the formats needed by the solvers used below.
Synthetic datasets are generated by running
```
python -m experiments.data.generate_synthetic -seeds [seeds]
```
The `-seeds` argument takes a list of integers to be used as the graph generators' seeds; in our experiments we use 15 seeds.
You can validate that your synthetic graphs have the expected vertex and edge counts by running
```
python -m experiments.data.validate -precomputed [ground_truth.csv]
```

## Reductions
### Run
Original datafiles are stored under `data/original`. However, all experiments are designed to run on
preprocessed data in `data/preprocessed`. To preprocess data, run
```
python -m experiments.preprocessing.run
```
This will process files from `huffner aa`, `huffner j`, `gka_0 - gka_34`, and `bqp50_0 - bqp100_10`
using Wernicke's and Akiba-Iwata's reduction techniques. The integrity of each preprocessed graph
will be verified by computing OCT using Akiba-Iwata's solver and verifying that the OCT set is valid
on the original graph.
Running preprocessing will result in the following directories in `data/preprocessed`:
* `/edgelist`
* `/huffner`
* `/lookup`
* `/oct`
* `/snap`
* `/summary`
`summary` contains lookup tables in CSV format for `huffner`, `gka`, and `beasley` data. The table
headers are
* Dataset
* vertices_removed
* edges_removed
* oct
* bipartite
The other directories contain a datafile in the corresponding data format for each preprocesed graph.
### Plot
The preprocessing `plot` script generates two tables.
1. `preprocessed_ground_truth.tex` containing metadata for all preprocessed graphs
2. `preprocessed_summary.tex` containing metadata for a subset of preprocessed graphs
## Validation
### Preprocessing
Preprocessing validation asserts that two directories containing preprocessed data could be isomorphic.
Relies on first having run preprocessing to generate a `data/preprocessed/` directory. Useful for checking
the results of preprocessing on multiple machines is consistent. To verify, run
```
python -m experiments.validation.preprocessing <dir 1> <dir 2>
```
### Results
Verifies that all computed OCT from the following files are valid OCT sets on the original graph.
* `combined_heuristics_experiment_results.csv`
* `exact_experiment_results.csv`
* `ilp_experiment_results.csv`
* `ic_baseline_experiment_results.csv`
* `ic_preprocessing_level.csv`

To validate results, run
```
python -m experiments.validation.results
```
## Exact
### Run
Exact experiments compare Akiba-Iwata, Huffner with preprocessing level 2, CPLEX with 4 threads,
and CPLEX with 1 thread by computing OCT with each on all preprocessed data with a timeout of
10 minutes (600 seconds). Results are written in CSV format to `exact_experiment_results.csv`.
Executions which hit the timeout are not recorded. The headers and data stored for each record are
| Header | Description |
| ------ | ----------- |
| Dataset | Dataset name without any extension (i.e. .huffner, .snap). |
| Solver | Solver used to compute solution. One of: akiba_iwata, ic, ilp, ilp_1t. |
| Time | Time (in seconds) needed to find an exact solution, rounded to the nearest decimal. |
| Size | Number of vertices found to be in OPT by the solver. |
| Certificate | A list of vertices in the computed OCT set in Python literal list syntax. |
An additional file, `ground_truth.csv`, is recorded containing Dataset, Size, and Certificate from
`exact_experiment_results.csv` for all Akiba-Iwata results. This is used as the ground truth OCT
size in other experiments.
Run exact experiments with
```
python -m experiments.exact.run
```
### Plot
The exact experiment plotting script generates the file `exact.tex` containing a latex formatted table
of rows with dataset, OPT, and solutions found by each solver. The plot script relies on the following
data files generated by running the exact experiment.
1. `exact_experiment_results.csv`
2. `ground_truth.csv`
To generate exact plots, run
```
python -m experiments.exact.plot
```
## Heuristic
### CPLEX
Uses CPLEX to compute OCT on all preprocessed datasets at timeouts of 0.01s, 0.1s, 1s, and 10s. Solutions
are written to `cplex_experiment_results.csv` with the following headers.
| Header | Description |
| ------ | ----------- |
| Dataset | Dataset name with file suffix. |
| Timeout | Time limit (in seconds). |
| Size | Number of vertices in the OCT set found by the solver. |
| Time | Time (in seconds) needed to find an exact solution, rounded to the nearest decimal. |
| Certificate | A list of vertices in the computed OCT set in Python literal list syntax. |
For CPLEX heuristic experiments, run
```
python -m experiments.heuristic.cplex
```
### Ensemble
Uses the Heuristic Ensemble to compute OCT on all preprocessed datasets at timeouts of 0.01s, 0.1s, 1s,
and 10s. Solutions are written to `heuristics_experiment_results.csv` with the following headers.
| Header | Description |
| ------ | ----------- |
| Dataset | Dataset name with file suffix. |
| Timeout | Time limit (in milliseconds). |
| Size | Number of vertices in the OCT set returned by the solver. |
| Time | Time (in milliseconds) needed to find the solution. |
| Certificate | A list of vertices in the computed OCT set in Python literal list syntax. |
For Ensemble heuristic experiments, run
```
python -m experiments.heuristic.ensemble
```
### Huffner
Uses Improved Huffner to compute OCT on all preprocessed datasets at timeouts of 0.01s, 0.1s, 1s, and 10s.
`preprocessing=1` is used with the lower two timeouts, `preprocessing=2` with the upper two. Solutions
are written to `ic_heuristics.csv` with the following headers.
| Header | Description |
| ------ | ----------- |
| Dataset | Dataset name without any extension (i.e. .huffner, .snap). |
| Solver | Which solver was used. One of (IC_1 or IC_2). |
| Timeout | Time limit (in seconds). |
| Time | Time (in seconds) needed to find a solution, rounded to the nearest decimal. |
| Size | Number of vertices in the OCT set returned by the solver. |
| Certificate | A list of vertices in the computed OCT set in Python literal list syntax. |
For Huffner heuristic experiments, run
```
python -m experiments.heuristic.huffner
```
### Combine Heuristics Data
A data processing and plotting script for the heuristics experiment. Relies on having the following
data files available.
* `ground_truth.csv` generated by running exact experiments
* `cplex_experiment_results.csv` generated by running CPLEX heuristic experiments
* `heuristics_experiment_results.csv` generated by running Ensemble heuristic experiments
* `ic_heuristics.csv` generated by running Huffner heuristic experiments
The data is first normalizes and combines all heuristics data and writes it to the csv file
`combined_heuristics_experiment_results.csv` with the headers
| Header | Description |
| ------ | ----------- |
| Dataset | Dataset name without any extension (i.e. .huffner, .snap). |
| Solver | Which solver was used. One of (HE, ILP, IC_1, or IC_2). |
| Timeout | Time limit (in seconds). |
| Time | Time (in seconds) needed to find a solution, rounded to the nearest decimal. |
| Size | Number of vertices in the OCT set returned by the solver. |
| Certificate | A list of vertices in the computed OCT set in Python literal list syntax. |
It also generates the latex tables `heuristic1.tex` and `heuristic2.tex`, which contain a summary
of heuristics experiment results for huffner datasets and bqp/gka datasets, respectively. Finally,
it computes the maximum approximation factor of each solver for every timeout and data group and
prints the result.
For plotting heuristic experiments, run
```
python -m experiments.heuristic.combine_heuristics_data
```
## Iterative Compression (IC)
### Baseline
Computes Huffner baseline data by running Improved Huffner with `preprocessing=0` (no preprocessing)
against Huffner experiment datasets. Datasets which take longer than 10 minutes (600 seconds) to
compute are timed out and not reported. For every dataset which OCT is computed, the results are
written to `ic_baseline_experiment_results.csv` with the headers
| Header | Description |
| ------ | ----------- |
| Dataset | Dataset name without any extension (i.e. .huffner, .snap). |
| Solver | Which solver was used (huffner_baseline). |
| Time | Time (in seconds) needed to compute OPT, rounded to the nearest decimal. |
| Size | Number of vertices in the OCT set returned by the solver. |
| Certificate | A list of vertices in the computed OCT set in Python literal list syntax. |
For baseline experiments, run
```
python -m experiments.ic.baseline
```
### Run
Runs Improved Huffner at `preprocessing=0`, `preprocessing=1`, and `preprocessing=2` against every
Huffner experiment dataset. Each preprocessing level computes OCT on a dataset 50 times using
seeds in the range `1-50`. The timeout used for each dataset is taken to be the largest of 0.01s,
0.1s, 1s, and 10s which is less than the time taken by Huffner at `preprocessing=0` to compute
an exact solution. I.E., we attempt to force Huffner to return an approximate solution. Relies on
the datafile `ic_baseline_experiment_results.csv` generated by running the Huffner baseline
experiment in order to determine the correct timeout.
Results are written to `ic_preprocessing_level.csv` with the following headers.
| Header | Description |
| ------ | ----------- |
| Dataset | Dataset name without any extension (i.e. .huffner, .snap). |
| Solver | Which solver was used (huffner). |
| Preprocessing | Preprocessing level used. One of 0, 1, or 2. |
| Timeout | Time limit (in seconds). |
| Seed | Seed value passed to Huffner. |
| Time | Time (in seconds) needed to compute the OCT set, rounded to the nearest decimal. |
| Size | Number of vertices in the OCT set returned by the solver. |
| Certificate | A list of vertices in the computed OCT set in Python literal list syntax. |
For Huffner experiments, run
```
python -m experiments.ic.run
```
### Plot
Summarizes Huffner experiment results. Requires the datafile `ic_preprocessing_level.csv` generated
by the Huffner experiment. Summarizes the mean, standard deviation, and quartiles of the size of the
returned OCT size in the latex table files
* `timeout_0.01.tex`
* `timeout_0.1.tex`
* `timeout_1.tex`
* `timeout_10.tex`
For Huffner plots, run
```
python -m experiments.ic.plot
```
## ILP
### Run
Runs CPLEX with 4 threads, CPLEX with 1 thread, and GLPK with 1 thread on ILP experiment datasets with a
10 minute timeout at 4MB and 16GB of memory. Problems are formulated as both VertexCover and OCT.
Results are written to `ilp_experiment_results.csv` with the following headers.
| Header | Description |
| ------ | ----------- |
| Solver | Which solver was used (huffner). |
| Threads | Number of threads each solver is allowed to use. |
| Memory | Memory limit (in MB). One of 4 or 16384. |
| Formulation | Problem formulation. One of VC or OCT. |
| Dataset | Dataset name without any extension (i.e. .huffner, .snap). |
| Vertices | Number of vertices in the OCT version of the graph. |
| Edges | Number of edges in the OCT version of the graph. |
| Time | Time (in seconds) needed to compute the OCT set, rounded to the nearest decimal. |
| Opt | Number of vertices in the OCT set returned by the solver. |
| Certificate | A list of vertices in the computed OCT set in Python literal list syntax. |
For ILP experiments, run
```
python -m experiments.ilp.run
```
### Plot
Parses ILP experiments data from `ilp_experiment_results.cvs` (generated by ILP experiments) and generates
`ilp_experiment.pdf`, `ilp_table.tex`, `ilp_experiment_4mb.pdf`, and `ilp_table_4mb.tex`. The first
two summarize ILP experiment data at a memory limit of 16GB, the second two at 4MB.
To generate ILP figures, run
```
python -m experiments.ilp.plot
```