## 2 Materials and Methods
### Some Theory to Justify the Choice of \(\varepsilon\)
Thus, the solution \(\hat{x}_{1},\ldots,\hat{x}_{n}\) cannot have a strictly better objective function value in the permuted problem \(P^{\prime}\) than does the original solution \(x_{1},\ldots,x_{n}\). From Theorem 3, it follows that the probability of finding any particular optimal solution is \(>0\). Nevertheless, the result is weak because the volume around the optimal solution in the proof depends on \(\varepsilon\), and hence, inversely on the coefficients. Next, we prove in two steps a stronger result about MORSE's capability to find different optima for the special case of 0-1 selection problems. Let \(P\) be a 0/1 ILP that is a selection and minimization problem with objective function \(\sum_{i=1}^{n}c_{i}x_{i}\), and every coefficient \(c_{i}=1\). Suppose one perturbs the objective function by multiplying each coefficient by some \(p_{i}\sim U(1-\varepsilon,1+\varepsilon)\) as the MORSE method does to arrive at the new problem \(\sum_{i=1}^{n}p_{i}x_{i}\). Then, any optimal solutions \(\{x_{j_{1}},x_{j_{2}},\ldots,x_{j_{d}}\}\) to the perturbed problem are optimal solutions to the original problem. The indices of the selected variables have the additional property that the sum of perturbed coefficients \(\sum_{k=1,d}p_{i}\) corresponding to the variables that are selected is minimized among all possible sums of \(d\) perturbed coefficients. Proof. : Since \(P\) is a selection problem, there must be some positive integer value \(d\), such that all optimal solutions are of size \(d\). By Theorem 1, any optimal solution to the perturbed problem is a solution to the original selection problem. Suppose the variables that are set to 1, and hence, selected in an optimal solution to the original problem are \(\{x_{j_{1}},x_{j_{2}},\ldots,x_{j_{d}}\}\). Then, the objective function value of that solution in the original problem is \(d\) and the objective function value of that solution in the perturbed problem is \(\sum\limits_{k=1}^{d}p_{j_{d}}\). Any solution that assigns 1 to exactly \(d\) variables in the perturbed problem will have an objective function value that is the sum of the perturbed coefficients for the \(d\) selected variables. Therefore, the optimal solutions of the perturbed problem are precisely those that minimize \(\sum\limits_{k=1}^{d}p_{j_{d}}\). It is possible that multiple solutions to the perturbed problem are tied for the minimum sum, although this is unlikely in practice. Let \(P\) be a 0/1 ILP that is a selection, minimization problem with objective function \(\sum_{i=1}^{n}c_{i}x_{i}\), and every coefficient \(c_{i}=1\). Suppose one perturbs the objective function by multiplying each coefficient by some \(p_{i}\sim U(1-\varepsilon,1+\varepsilon)\) as the MORSE method does. Suppose (as explained in the Proof of Lemma 1) that all optimal solutions have objective function value \(d\) meaning that exactly \(d\) variables have value \(1\). Suppose \(\{x_{j_{1}},x_{j_{2}},\ldots,x_{j_{d}}\}\) and \(\{x_{k_{1}},x_{k_{2}},\ldots,x_{k_{d}}\}\) are two distinct optimal solutions of the original problem. Then, the probabilities that \(\{x_{j_{1}},x_{j_{2}},\ldots,x_{j_{d}}\}\) and \(\{x_{k_{1}},x_{k_{2}},\ldots,x_{k_{d}}\}\) are optimal solutions of one problem perturbation from MORSE are equal. Proof. : Let \(M_{j}\) be the set of perturbations that make \(V_{j}=\{x_{j_{1}},x_{j_{2}},\ldots,x_{j_{d}}\}\) optimal for the perturbed problem. Let \(M_{k}\) be the set of perturbations that make \(V_{k}=\{x_{k_{1}},x_{k_{2}},\ldots,x_{k_{d}}\}\) optimal for the perturbed problem. We show constructively that there is a one-to-one correspondence \(C:M_{j}\to M_{k}\). It follows that the probability that a uniformly randomly selected perturbation is in \(M_{j}\) equals the probability that a uniformly randomly selected perturbation is in \(M_{k}\). Let \(p_{j}\) be a perturbation of coefficients in \(M_{j}\). We construct a corresponding perturbation \(p_{k}\) in \(M_{k}\).