## 2 Materials and Methods
### Figures of Merit Used in Testing  
As explained in Section 1, there are three freely available methods against which we can compare: the solution pool in Gurobi, the count function in SCIP, and the populate function in CPLEX. Since we implemented MORSE using Gurobi, most of our tests were executed in comparison to the solution pool method.  
We compared the performance of our perturbation method against the standard, unperturbed method using the following test design. We executed \(r\) runs in parallel and obtained \(s\) optimal solutions, not necessarily distinct. We considered two figures of merit.  
First, we examined the number of distinct optima found at least once among the \(s\) optimal solutions. Two solutions are considered distinct if and only if they differ in the value of at least one variable appearing in the objective function.  
Second, we compared the solution sets on two previously used measures of diversity: _Hamming distance_ and _Shannon entropy_. Solution set diversity has been previously quantified by average Hamming distance between solution vectors (see [5; 6]).  
**Definition 1** (Hamming distance).: _For solution vectors \(x=[x_{1},\ldots,x_{n}]\) and \(y=[y_{1},\ldots,y_{n}]\), the Hamming distance \(H(x,y)\) is given by:_  
\[H(x,y)=\sum_{i=1}^{n}f(x_{i},y_{i})\quad\text{where }f(x,y)=\begin{cases}1,&x \
eq y\\ 0,&x=y\end{cases}\]  
For example, consider solution vectors \(A=[1,2,3,4]\) and \(B=[1,0,3,5]\); \(H(A,B)=2\). The Hamming distance does not consider the magnitude of the difference between integer variables, and is increased by a uniform increment of 1 for each integer variable that differs between solutions.  
**Definition 2** (Shannon entropy).: _Let \(\mathcal{X}=\{x_{1},x_{2},\ldots,x_{k\leq t}\}\) be the set of solution vectors. The Shannon entropy is defined as follows._  
\[S(\mathcal{X})=-\sum_{x\in\mathcal{X}}p_{x}\log_{2}(p_{x})\]In some other applications, the Shannon entropy is denoted by \(H\), but we use the mnemonic \(S\) for the Shannon entropy and reserve the mnemonic \(H\) for the Hamming distance. For example, if there exist two solutions that are found with probabilities \(1/3\) and \(2/3\), then the Shannon entropy is as follows.  
\[S(\mathcal{X})=-\bigg{(}\frac{1}{3}\log_{2}\frac{1}{3}+\frac{2}{3}\log_{2} \frac{2}{3}\bigg{)}\approx 0.918\]  
In our analysis, we are interested in the entire solutions as combinatorial objects. If instead there are three solutions and each solution occurs with probability \(1/3\), then the Shannon entropy of the solution set is as follows:  
\[S(\mathcal{X})=-3\bigg{(}\frac{1}{3}\log_{2}\frac{1}{3}\bigg{)}\approx 1.585\]  
Suppose, instead, we sample siux not necessarily distinct solutions, and we observe the distinct solutions \(A,B,C\) three times, two times, and one time, respectively. Then, the Shannon entropy of the solution multiset would be as follows:  
\[-\bigg{(}\frac{1}{2}\log_{2}\frac{1}{2}+\frac{1}{3}\log_{2}\frac{1}{3}+\frac{1 }{6}\log_{2}\frac{1}{6}\bigg{)}\approx 1.459\]  
We found one analysis of a problem-specific method to find multiple optima that used (higher) Shannon entropy on the values of individual variables among solutions as a figure of merit [10]. However, we did not find any previous study of multiple optima in MIPs that used Shannon entropy on the multiplicity of solutions, as in our study. In general, higher Hamming distance and higher Shannon entropy are preferable in that they indicate higher diversity. When comparing the Hamming distance or Shannon entropy for solution sets found by the two methods, we do not normalize by the number of distinct solutions found.