Modeling floor function exactly

Question

Suppose we want to enforce a constraint $$ y=\lfloor{x}\rfloor $$ where $x$ is some continuous variable. One option is to use $$ x-1\leq{y}\leq{x},\quad y\in\mathbb{Z}, $$ which fails on the edge case $x\in\mathbb{Z}$. One way around this which works approximately is to introduce some tolerance $\varepsilon>0$ and enforce $$ x-1+\varepsilon\leq{y}\leq{x},\quad y\in\mathbb{Z}, $$ which fails if $x\in(\lceil{x}\rceil-\varepsilon,\lceil{x}\rceil)$. Is there an exact way to enforce a floor function, perhaps by introducing additional integer variables?

Answer 1

It is not possible to model the floor function as a constraint without modeling strict inequality. To prove this, I will show how the floor function can be used to model strict inequalities.

Thanks to @Rob Pratt for showing a cleaner formulation that does not need a possibly large M.

Suppose we can model the constraint $y=\lfloor x\rfloor$ for any real variable $x$ and integer variable $y$. First note that if we have the floor over the real numbers, we have the ceiling as well, since $\lceil x\rceil = -\lfloor -x\rfloor$. This means we can add constraints $\lceil x\rceil -\lfloor x\rfloor =1$, which is equivalent to $x\notin \mathbb{Z}$. The statement $0<x$ for a real variable $x$ is equivalent to $0\leq x \wedge (1\leq x \vee x\notin \mathbb{Z})$. So, we can encode the statement $0<x$ as follows:

$\begin{align*}0&\leq x\\ 1-M\cdot (1-b_1)&\leq x\\ b_2 &= \lceil x\rceil -\lfloor x\rfloor\\ b_1 + b_2&\geq 1, \end{align*}$

However, since $x$ is required to be positive in all cases, we can set $M$ to $1$ to obtain the following formulation:

$\begin{align*}b_1&\le x \\ b_2 &= \lceil x \rceil - \lfloor x \rfloor \\ b_1 + b_2 &\ge 1\end{align*}$

using only the additional binary variables $b_1,b_2$. As any strict inequality can be modeled via $0<x$, we are done.

In other words, if we assume we cannot model strict inequalities, then we cannot model a floor function.

---

Intuitively, what is going on here is that the floor function constraint is as 'powerful' as strict inequalities or integrality testing. Or, to speak in CS terms, all these constraints can be reduced to each-other and lie in the same equivalence class. (cf. complexity classes and poly-time reductions) I wonder if someone investigated these 'expressibility classes' in the context of linear programming before.

---

@Rob Pratt notes that we can even do without the additional binary variables and write the constraint $0<x$ as the single constraint $1-\lceil x\rceil + \lfloor x \rfloor \leq x$. However, note that even after removing the binary variables this reduction still only makes sense in the context of integer programming, as flooring an otherwise unconstrained real variable yields an unconstrained integer variable.

Answer 2

I think you can resort to bilevel optimization, in the spirit of slide 3 here

In bilevel optimization, some variables are the optimal solutions of another optimization problem called "the follower subproblem".

In our case, one can define the following follower subproblem:

$$y = \underset{y'}{\operatorname{argmax}} \left\{ y': y' \le x, \ y' \hbox{ integer} \right\}$$

This should work also if $x=(x_1, \dots\,x_n)$ is an $n$-dimensional vector, i.e., you can set-up a single follower problem to define all the rounded $y_i$'s:

$$y = \underset{y'}{\operatorname{argmax}}\left\{ \sum_{i=1}^n y'_i: y' \le x, \ y' \hbox{ integer}\right\}$$

Whether this is useful in practice I don’t know.

Answer 3

As all have mentioned, the problem is intrinsically hard, as it effectively involves a strict inequality.

One way to represent it, using no strict inequalities or magic constants, is to use the simple trick that $> 0$ can be replace with $\geq e^{-z}$ for a new decision variable $z$. An exact solver (not allowed to work with infinities) could then never return a non-strict solution.

Here, that would translate to $x-1 + e^{-z} \leq y \leq x$. Nice convex exponential cone relaxation and all.

Of course, a practical exact solver would not be able to work exactly with expressions involving exponentials, so this is just silly acrobatics trying to avoid introducing some kind of tolerance in the end, i.e., a magic constant.

EDIT: A solution which (in theory...) can be implemented and wouldn't force you out in the transcendental world is to use $x-1 + z^{-2} \leq y \leq x$

Answer 4

You only specified $x$ is "continuous". I'll interpret this as $x$ is rational rather than real. This is not a terrible assumption, as floating point numbers in computers are rational anyways.

A rational $x$ can be replaced by a fraction of two integers $x = \frac{p}{q}$ with $p$ free and $q$ positive.

Now the constraint is $y = \left\lfloor \frac{p}{q}\right\rfloor$. This is equivalent to the two constraints

\begin{cases}y = \frac{p - m}{q}\\m = p \mod q\end{cases} where $m$ is another integer variable.

Let's introduce yet another (non-negative) integer variable $a$ and additional constraints to get rid of modulo operator. \begin{cases}p = a \cdot q + m\\m \leq q - 1\end{cases}

So finally we can replace the constraint $y = \lfloor x \rfloor$ by

\begin{cases}x = \frac{p}{q}\\y = \frac{p-m}{q}\\p = a \cdot q + m\\m \leq q - 1\end{cases} where $p$ is a free integer and $a,m,q$ are positive integers.

Of course, this is no longer linear and quite ugly to solve. In implementations it will bring tolerances back when approximating the nonlinear constraints.

Answer 5

$x-1 <y \leq x \implies y \leq x < y+1\implies 0\leq x-y <1$. We then can set $y\in \mathbb {Z} $.

Answer 6

I think the answer of Rob can be developed into an exact answer, if we can ascertain apriori that the fractional part $s$ can be no larger than a given bound.

Consider $x$ to be the floor of $y$. Further assume we can guarantee that $x$ does not lie in the following range (Integer + $\delta$, Integer+1] for any Integer. This assumption can be stated also as: $0 \le \delta <1$ is the largest possible value for the fractional part of $x$. Of course this is a hard condition to satisfy, but for many problems it can be easy. For example, consider this question: https://math.stackexchange.com/questions/3520916/proof-for-an-easy-empirical-result-on-fractions-and-ceilings

Then $x-\delta \le y \le x$ and $y \in Z^+$ model the floor exactly.

Answer 7

It is solved by introducing a slack variable, one simple explanation is here and a more detailed video tutorial is here (with online solver).

Alternative (homework preventing) example:

How to implement the Ceiling function in a Mixed Integer Program model.

The constraint in question is:

$$\left\lceil\frac{x - A}{B}\right\rceil \cdot C + D \cdot x \lt E$$

Answer:

Introduce an integer variable $y$ and a continuous slack variable $s$ and write:

\begin{align}y \cdot C + D \cdot x &\leq E\\y&=\frac{x-A}{B}+s\\s &\in [0,0.999]\\y &\in \{\dots,−3,−2,−1,0,1,2,3,\dots\}\end{align}

Note that $\lt$ constraints are no good, so we make that $\leq$. We have a very small area for $s$ that we don’t allow: between $0.999$ and $1$. This is to prevent that the ceiling of an integer $k$ is the next integer $k+1$.

Answer 8

An answer with no $\epsilon$:

We can set $y+s=x $, $y \in \mathbb {Z} $, $s\geq 0$.

Appropriate terms (appropriate in terms of sign for following terms, values for big-M's and minimization and maximization) have to be added in the objective function such as $M_1x$, $M_2y$ based on the sign of $x$ in the objective function and bounds on $x$.

In the general case one can add these two terms somehow $x$ and $y$ have the same magnitude of increase in OF in both terms value and sign, if minimization $-M_1x$, $-M_2y$ and maximization $M_1x$, $M_2y$.