numerical instability of integer programming

Question

Let us assume the objective function $f$ of some IP looks as follows $$ f = \sum x_i + \varepsilon \sum y_i.$$ With $\varepsilon$ being very small ($\approx 0.00001$) and $x_i$ and $y_i$ some variables. There may also be some constraints, but let us not focus on them. It seems that IP-solvers have problems to solve such an IP, because of numerical instability. (I am by now means an expert on IP solvers.)

Is there a way to reformulate the IP, such that the IP can still be solved efficiently?

The purpose of the small $\varepsilon$ is to make minimizing the $\sum y_i$ a secondary priority. In other words, among the solutions that minimize $\sum x_i$, try to minimize $\sum y_i$.

Answer 1

You can try doing it in two stages. First solve the problem with the original objective to minimize $\sum x_i$ and original constraints. Suppose the optimal solution has $\sum x_i = s$. Then solve the problem with additional constraint $\sum x_i = s$ and objective to minimize $\sum y_i$.

Answer 2

I think that indeed the small value of epsilon is the problem. My suggestion is to change the objective to $M \sum x_i + \sum y_i$, where $M$ is a big number (at least big enough to prioritize $\sum x_i$ over $\sum y_i$. This has been applied in examples where $x_i >0$ means infeasibilty e.g. because $x_i$ signals that something in unassigned.