## 2 Materials and Methods
### Some Theory to Justify the Choice of \(\varepsilon\)
The idea behind the proof of Theorem 1 can be generalized to fractional coefficients by scaling up the problem by multiplying all the coefficients by the least common multiple of the denominators. For example, if the objective function is \(1.3x+3.2y+2.1z\), which is equivalent to \(\frac{13}{10}x+\frac{16}{5}y+\frac{21}{10}z\), and the least common multiple of the denominators is \(10\). We can scale up the objective function to \(13x+32y+21z\) to make the adjusted coefficients integral and then, Theorem 1 applies to the adjusted problem. As shown in the examples above in Section 2.2, the consequence of multiplying the coefficients by \(10\) is to divide \(\varepsilon\) by \(10\). The scaling procedure is specified by Algorithm 1. Preservation of optima after perturbing coefficients for continuous variables cannot be guaranteed because the difference in objective function values for two solutions could be infinitesimally small. When there are continuous variables, MORSE checks that potential solutions are optimal (to within machine tolerance) for the original problem. For the proof of Theorem 1, we assumed that one optimal solution is available and we used the bound \(\varepsilon<\left(2\sum_{i=1}^{n}|c_{i}x_{i}|\right)^{-1}\) without assuming any bounds on the variables \(x_{i}\). If upper and lower bounds on variables are available, as is the case for MIPLIB, then we can instead use the formulation in Section 2.2 and the same reasoning applies. Using the available bounds on the variables simplifies MORSE because one does not need a sequential phase of finding one optimal solution before the subsequent phase of running multiple parallelized runs to obtain multiple optimal solutions. Next, we prove, in theory, that MORSE can find any optimal solution. Theorem 2: _For any optimum \(x_{1},\ldots,x_{n}\) of \(P\), there exists a perturbation \(c^{\prime}{}_{1},\ldots,c^{\prime}{}_{n}\) such that \(x_{1},\ldots,x_{n}\) is also an optimum of \(P^{\prime}\)_  
Proof: Choose the identity perturbation such that \(c^{\prime}{}_{1}=c_{1},\ldots,c^{\prime}{}_{n}=c_{n}\). Then \(P=P^{\prime}\) and optima are conserved. Next, we consider the effects of non-identity perturbations in breaking ties. Theorem 3: _Suppose the instance \(P\) is defined as in Theorem 1. For any optimum \(x_{1},\ldots,x_{n}\) of \(P\), there exists a perturbation \(c^{\prime}{}_{1},\ldots,c^{\prime}{}_{n}\) such that \(c^{\prime}{}_{1}\
eq c_{1},\ldots,c^{\prime}{}_{n}\
eq c_{n}\) and \(x_{1},\ldots,x_{n}\) is also an optimum of \(P^{\prime}\)._  
Proof: Let \(\varepsilon\) be defined as in the proof of Theorem 1. Define \(c^{\prime}{}_{i}= \begin{cases}(1+\varepsilon)\cdot c_{i},&c_{i}x_{i}>0,\\ (1-\varepsilon)\cdot c_{i},&c_{i}x_{i}<0.\end{cases} \)  
If the values of \(x_{i}\) remain unchanged, then the constraints of \(P^{\prime}\) remain satisfied. Moreover, any solution that satisfies the constraints of \(P\) also satisfies the constraints of \(P^{\prime}\). By this perturbation, \(c^{\prime}{}_{1}x_{1}+\ldots+c^{\prime}{}_{n}x_{n}>c_{1}x_{1}+\ldots+c_{n}x_ {n}\). Hence, because of the choice of \(\varepsilon\), the absolute net change in the objective function value, which is given by \(\varepsilon\sum\limits_{i=1}^{n}|c_{i}x_{i}|\), is less than 1. Aiming to find a contradiction, suppose that some other solution \(\hat{x}_{1},\ldots,\hat{x}_{n}\) yields a higher objective function than \(x_{1},\ldots,x_{n}\). Consider the difference in objective function value of this solution for the original instance \(P\) and the perturbed instance \(P^{\prime}\). For each of the \(k\) terms involving an integer-constrained variable, if \(c_{i}\hat{x}_{i}>0\), then \(|c_{i}\hat{x}_{i}-c^{\prime}_{i}\hat{x}_{i}|\leq\varepsilon c_{i}\hat{x}_{i}\). Therefore, the net increase in objective function value for \(\hat{x}_{1},\ldots,\hat{x}_{n}\leq\sum\limits_{i=1}^{n}|c_{i}x_{i}|\).