The set of all stable matchings of an instance \(I\)  of smi were found using [1]}'s \(O(m + n|\mathcal {M}_S|)\)  time Enumeration Algorithm [1]}. The Enumeration Algorithm comprises two runs of the extended Gale-Shapley Algorithm [3]} (finding both the man-optimal and woman-optimal stable matchings), one run of
the Minimal Differences Algorithm [4]} (finding all rotations of an instance), creation of the rotation digraph, and finally enumeration of all stable matchings using this digraph [1]}.
Using the list of enumerated stable matchings we were then able to compute all the types of optimal stable matchings described above.
A timeout of 1 hour was used for this algorithm. Note that since the time complexities of the algorithms described in this paper do not beat the best known for these problems, we did not implement our algorithms to test their performance.
Experiments were carried out on a machine with 32 cores, 8\(\times \) 64GB RAM and Dual Intel® Xeon® CPU E5-2697A v4 processors, running Ubuntu version \(17.10\) . Instance generation and statistics collection programs were written in Python and run on Python version \(2.7.14\) . The plot and table generation program was written in Python and run using Python version 3.6.1. All other code was written in Java and compiled using Java version \(1.8.0\) . All Java code was run on a single thread, with GNU Parallel [6]} used to run multiple instances in parallel. Java garbage collection was run in serial and a maximum heap size of 1GB was distributed to each thread. Code and data repositories for these experiments can be found at https://doi.org/10.5281/zenodo.2545798 and https://doi.org/10.5281/zenodo.2542703 respectively.
