## 2 Materials and Methods  
### Perturbing the Coefficients in the Objective Function  
We present an algorithm, MORSE, to map random perturbations to the coefficients on the binary and integer objective function variables to efficiently find distinct optima for ILP instances with multiple optima. One theory, described below, assumes that variables are restricted to be integers, though our implementation allows continuous variables without perturbing the coefficients of continuous variables. In either case, MORSE always returns an optimal solution. When there are continuous variables, the MORSE software, version 1 checks that optimality is preserved. We refer to the Gurobi single-solution or solution pool method as the conventional _homogeneous/uniform weights method_, in which we solve the problem in its original, unmodified form. In particular, Gurobi does not alter the original coefficients of binary or integer variables in the objective function. In practice, one can obtain multiple solutions via the homogeneous weights method by varying the Gurobi random seed and/or by using the solution pool. In our experiments, we varied the random seed and obtained one solution per Gurobi run to facilitate a head-to-head comparison with MORSE. We use the term _homogeneous/uniform weights_ because leaving the original coefficients unchanged is equivalent to multiplying all the coefficients by 1 homogeneously or uniformly.  
Central to MORSE is the selection of a small value \(\varepsilon>0\) that determines the maximum extent to which the coefficients may be varied, as explained first with an example and subsequently with formulae.  
Consider the following instance:  
\[\text{maximize} x_{1}+x_{2}\] subject to the constraints \[x_{1},x_{2}\leq 2,\] \[x_{1}+x_{2}\leq 3.5,\] \[x_{1},x_{2}\in\mathbb{Z}.\]  
The objective function can be expressed as \(c^{T}x\), where \(c=\begin{pmatrix}1\\ 1\end{pmatrix}\) and \(x=\begin{pmatrix}x_{1}\\ x_{2}\end{pmatrix}\). Suppose we choose \(\varepsilon=0.01\). Next, we generate a random _perturbation vector_\(v\stackrel{{ iid}}{{\sim}}U(1-\varepsilon,1+\varepsilon)=U(0.99,1.01)\). If all variables are integral, then \(\dim(v)=\dim(x)\), which is the number of variables in the objective function. If there are continuous variables, \(\dim(v)\) is the number of binary or integer variables (defined formally below).  
An example of such a perturbation vector is \(v_{1}=\begin{pmatrix}0.99864\\ 1.00142\end{pmatrix}\).  
We subsequently define the perturbed coefficient vector \(c_{1}^{\prime}=v_{1}^{T}c=\begin{pmatrix}0.99864\\ 1.00142\end{pmatrix}\).  
This yields the perturbed objective function \(c_{1}^{\prime T}x=0.99864x_{1}+1.00142x_{2}\). Without modifying the constraints, we solve the resulting instance and obtain the optimum \(\{x_{1}=1,x_{2}=2\}\).  
On another execution of MORSE, with the same value for \(\varepsilon\), imagine that we generate the perturbation vector \(v_{2}=\begin{pmatrix}1.00045\\ 0.99312\end{pmatrix}\). Following the same steps as above, we obtain the optimum \(\{x_{1}=2,x_{2}=1\}\).  
By executing two independent runs of MORSE, we can find the two distinct optima for the provided instance. To generalize this notion, for any instance with \(s>1\) distinct optima, we can try to find all distinct optima in \(r\geq s\) independent MORSE runs.