1
$\begingroup$

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

$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Jul 3, 2020 at 16:05
2
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.