Modeling various non-differentiable functions is quite common knowledge including $\operatorname{abs}$, $\min$ and $\max$ functions. How would one go about modeling the nearest integer function, say in an inequality constraint $\lfloor{x}\rceil \leq C$?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Do you have a specific rounding rule in mind for .5 cases? The Wikipedia page on 'Nearest integer function' (en.wikipedia.org/wiki/Nearest_integer_function) says "On most computer implementations, the selected rule is to round half-integers to the nearest even integer" $\endgroup$ – Dipayan Banerjee Oct 12 '19 at 20:51
-
$\begingroup$ @DipayanBanerjee Yes, let's assume the nearest even integer rule for this example. $\endgroup$ – Josh Allen Oct 12 '19 at 20:55
-
$\begingroup$ Pardon the beginner's question of a passer-by, what does "modeling" mean in this context? Is it simply the process of expressing some transformation as an algebraic function? $\endgroup$ – Violet Giraffe Oct 13 '19 at 19:24
Add a comment
|
$\begingroup$
$\endgroup$
This is a hack of Robert Schwarz's answer, to accommodate the "round .5 to even" rule. We introduce integer variable $y$ and binary variable $z$, along with the constraints $$2y+z \le x \le 2y + z + 1$$ and $$x + z - 0.5 \le C.$$ If $x$ is noninteger, the first constraint finds the nearest integers on either side. If the floor of $x$ is even (meaning a fraction of one half would round down), $z=0$ and we require that $x - 0.5 \le C$. If the floor of $x$ is odd (meaning a fraction of one half would round up), $z=1$ and we require that $x + 0.5 \le C$.
There is an ambiguity when $x$ is integer. For instance, if $x = 3$, both $(y,z)=(1,1)$ and $(y,z)=(1,0)$ satisfy the constraint. Fortunately, the solver will bail us out: if it "wants" to have $x=3$ be feasible (and if $C=3$), it will choose $(y,z)=(1,0)$, so that $x=3=C$ satisfies the second constraint.
$\begingroup$
$\endgroup$
Assuming finite bounds on $x$, this could be modeled with disjunctions on the many cases to which $x$ can be rounded.
For example, if $x \in [ 0, 2 ]$, we would have: $$ \begin{cases} x \le 0.5, & 0 \le C \\ 0.5 \le x \le 1.5, & 1 \le C \\ 1.5 \le x , & 2 \le C \end{cases} $$
The disjunction itself could be modeled with auxiliary binary variables and big-$M$ constraints, for example.
Note that rounding in this context has some ambiguity, as a value of $0.5$ may be rounded either to $0$ or $1$, because strict inequalities can usually not be enforced by MIP solvers.
$\begingroup$
$\endgroup$
1
As an alternative solution, I propose to add an auxiliary integral variable $y \in \mathbb{Z}$ that should play the role of the rounded $x$.
For your example of the inequality, I would add: $$ \begin{array}{rll} y &\le& C \\ x - 0.5&\le& y \end{array} $$
-
3$\begingroup$ This is close, but trips over the "round-to-even" rule. We can assume that $C$ is integer. Suppose that $C=3$. $x=3.5$, $y=3$ satisfies both inequalities, but $\left\lceil x\right\rfloor =4$. $\endgroup$ – prubin Oct 12 '19 at 22:35
$\begingroup$
$\endgroup$
Assuming that the value $C + 0.5$ is valid, you could model this by simply adding the constraint
$$x \leq C + 0.5$$
Otherwise, you define a constant say $\epsilon = 10^{-7}$ and do
$$x \leq C + 0.5 - \epsilon$$
