## 2 Materials and Methods
### Some Theory to Justify the Choice of \(\varepsilon\)  
Our intuition is that by making \(\varepsilon\) sufficiently small, any optimum with the perturbed objective function will also be an optimum for the original objective function. We prove that optima are preserved for ILPs with integer coefficients in Theorem 1. However, the converse is untrue; for any specific perturbation of the objective function, only some optima for the original problem may remain optima for the perturbed problem, as shown in the example above, in which a perturbation preserves one possible optimum, but not the other. Our intuition is that some partial converse holds such that, for every optimum of the unperturbed problem, there exist perturbations that retain that optimum; this intuition is partly formalized in Theorems 2 and 3. When there are continuous variables, however, our implementation checks that optima are conserved, because this cannot be guaranteed. **Theorem 1**. : _Suppose all the coefficients in the original problem are integers, all the variables are binary or integer, and the problem \(P\) is a maximization problem. There exists a sufficiently small \(\varepsilon>0\) such that for any perturbation \(c_{1},\ldots,c_{n}\to c^{\prime}{}_{1},\ldots,c^{\prime}{}_{n}\) and any resulting optimum \(x^{\prime}{}_{1},\ldots,x^{\prime}{}_{n}\) of the perturbed instance \(P^{\prime}\), \(x^{\prime}{}_{1},\ldots,x^{\prime}{}_{n}\) is also an optimum of the original instance \(P\)._  
Proof. : Let \(x_{1},\ldots,x_{n}\) be an optimum of \(P\). Define \(\varepsilon<(2\sum_{i=1}^{n}|c_{i}x_{i}|)^{-1}\) and let \(P^{\prime}\) be the perturbed instance of \(P\) with respect to \(\varepsilon\). Consider \(x^{\prime}{}_{1},\ldots,x^{\prime}{}_{n}\) such that \(x^{\prime}{}_{1},\ldots,x^{\prime}{}_{n}\) is optimal for \(P^{\prime}\) but is not optimal for the original instance \(P\). Due to the integrality constraints, the assumption that the coefficients are integers, the assumption that the variables are not continuous, and the assumption that the problem is a maximization problem,  
\[P\Big{(}x_{1},\ldots,x_{n}\Big{)}-P\Big{(}x^{\prime}{}_{1},\ldots,x^{\prime}{ }_{n}\Big{)}\geq 1. \tag{1}\]  
Consider what happens to these values in the perturbed problem \(P^{\prime}\). Seeking a contradiction, suppose that \(x^{\prime}\) has a better objective function value than \(x\) for \(P^{\prime}\), then  
\[P^{\prime}\Big{(}x^{\prime}{}_{1},\ldots,x^{\prime}{}_{n}\Big{)} -P^{\prime}\Big{(}x_{1},\ldots,x_{n}\Big{)} \leq\bigg{[}P\Big{(}x^{\prime}{}_{1},\ldots,x^{\prime}{}_{n}\Big{)} -P\Big{(}x_{1},\ldots,x_{n}\Big{)}\bigg{]}\] \[\quad+\bigg{[}\Big{|}P^{\prime}\Big{(}x_{1},\ldots,x_{n}\Big{)}-P \Big{(}x_{1},\ldots,x_{n}\Big{)}\Big{|}\bigg{]}\] \[\quad+\bigg{[}\Big{|}P^{\prime}\Big{(}x^{\prime}{}_{1},\ldots,x^{ \prime}{}_{n}\Big{)}-P\Big{(}x^{\prime}{}_{1},\ldots,x^{\prime}{}_{n}\Big{)} \Big{|}\bigg{]}\] \[<-1+\frac{1}{2}+\frac{1}{2}\] \[<0 \tag{2}\]  
Because we assumed the original problem \(P\) as a maximization problem, this is a contradiction. The first term in square brackets is at most \(-1\) based on Equation (1). The second and third terms in square brackets are \(<\)1/2 due to the definition of \(\varepsilon\). In our experiments, most instances are minimization problems, due to the structure of MIPLIB, so we must also consider the complementary case in which \(P\) is a maximalization problem. For the latter case, the first numbered inequality (Equation (1)) becomes, instead  
\[P\Big{(}x^{\prime}{}_{1},\ldots,x^{\prime}{}_{n}\Big{)}-P\Big{(}x_{1},\ldots,x_ {n}\Big{)}\geq 1\]  
and the subsequent contradiction (Equation (2)) is that  
\[P^{\prime}\Big{(}x_{1},\ldots,x_{n}\Big{)}-P^{\prime}\Big{(}x^{\prime}{}_{1}, \ldots,x^{\prime}{}_{n}\Big{)}<0\]  
meaning that the original solution has a lower (better for minimization) objective function value than the alternative solution. The assumption that all the coefficients for the integer-constrained variables are themselves integral does not hold for some MIPLIB instances.