8
$\begingroup$

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

$\endgroup$
  • 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 at 20:51
  • $\begingroup$ @DipayanBanerjee Yes, let's assume the nearest even integer rule for this example. $\endgroup$ – Josh Allen Oct 12 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 at 19:24
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 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 at 22:35
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.