8

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

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Josh Allen
  • 725
  • 3
  • 14
  • 1
    Do you have a specific rounding rule in mind for .5 cases? The Wikipedia page on 'Nearest integer function' (https://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" – dxb Oct 12 '19 at 20:51
  • @DipayanBanerjee Yes, let's assume the nearest even integer rule for this example. – Josh Allen Oct 12 '19 at 20:55
  • 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? – Violet Giraffe Oct 13 '19 at 19:24

4 Answers4

6

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.

prubin
  • 39,078
  • 3
  • 37
  • 104
5

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.

Robert Schwarz
  • 2,316
  • 8
  • 21
2

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

Robert Schwarz
  • 2,316
  • 8
  • 21
  • 3
    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$. – prubin Oct 12 '19 at 22:35
1

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

Claudio Contardo
  • 1,574
  • 6
  • 13