1

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$.

Till
  • 504

2 Answers2

4

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$.

Robert Israel
  • 448,999
  • For numerical reasons, I would probably write the new constraint as $\sum_i x_i \le s + \delta$ with $\delta$ small enough that getting a solution with $\sum_i x_i = s + \delta$ would not keep me up at night. – prubin Jul 03 '20 at 16:05
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.

Marjan van den Akker
  • 21