29
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ My answer is incorrect. I've been trying to salvage it but haven't figured out how yet. You should un-accept my answer, and I will delete it. I'll post a new one if I ever figure it out. $\endgroup$ – LarrySnyder610 Jun 14 at 1:22
  • $\begingroup$ @LarrySnyder610 Oh too bad! I’ll keep my eye out $\endgroup$ – David M. Jun 14 at 1:26
  • 2
    $\begingroup$ On the plus side, looks like I'll earn my Disciplined badge. $\endgroup$ – LarrySnyder610 Jun 14 at 1:35
  • 1
    $\begingroup$ As one answer shows, you can easily do this when you can enforce a strict inequality over continuous variables. Your $\varepsilon$ trick looks like a way to work around not being able to do that. It might be a good idea to indicate if strict inequalities don't work for you, if that is indeed the case. $\endgroup$ – Discrete lizard Jun 14 at 7:20
  • 5
    $\begingroup$ If you want to use this in a solver you'll have to work with the (carefully chosen) epsilon approach as it is not possible (due to machine precision) to have a real " strictly less than" constraint - only "less or equal" than constraints are meaningful. $\endgroup$ – JakobS Jun 14 at 8:41
16
+100
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Conjunctive normal form of your logical proposition leads to the following slightly simpler formulation: \begin{align*} 0 &\le x \\ 1 - M \cdot(1-b_1)&\le x \\ b_3 &= \lceil x \rceil - \lfloor x \rfloor \\ b_1 + b_3 &\ge 1\end{align*} $\endgroup$ – Rob Pratt Jun 16 at 14:35
  • 5
    $\begingroup$ And then taking $M=1$ simplifies further: \begin{align*} b_1&\le x \\ b_3 &= \lceil x \rceil - \lfloor x \rfloor \\ b_1 + b_3 &\ge 1\end{align*} $\endgroup$ – Rob Pratt Jun 16 at 14:44
  • $\begingroup$ @RobPratt Ah yes, you are right, we don't even need big-M when we already require x is positve. That dependency on big-M did seem weird. This makes it a lot cleaner, thanks! $\endgroup$ – Discrete lizard Jun 16 at 14:51
  • $\begingroup$ This is nice. I have to think about it a bit more but I think I am convinced. $\endgroup$ – LarrySnyder610 Jun 16 at 20:10
  • 3
    $\begingroup$ In fact, I guess we can eliminate the binary variables and just have $$1-\lceil x \rceil +\lfloor x \rfloor \le x.$$ $\endgroup$ – Rob Pratt Jun 17 at 3:20
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How is this exact given non-zero achieved integrality (etc.) tolerances? $\endgroup$ – Mark L. Stone Jun 17 at 11:27
  • 3
    $\begingroup$ Well, the question asked for an exact formulation without tolerances, as the bilevel one. I agree that solving in practice that formulation brings tolerances back (see the last line in my answer) but I doubt you can get anything practical without tolerances and/or assumptions on x. $\endgroup$ – Matteo Fischetti Jun 17 at 11:44
  • $\begingroup$ I think this approach works. It is much harder to solve than introducing new binary variables, big-Ms, etc., as you pointed out, but I think this answer also makes sense in light of @Discrete lizard's answer, i.e., that floor is somehow fundamentally harder than, say, other logical constraints. $\endgroup$ – LarrySnyder610 Jun 17 at 12:51
  • 1
    $\begingroup$ @LarrySnyder610 Or in particular, that it is about as hard as modeling a strict inequality, which via my answer + this answer can also be done with bi-level optimisation. In that way, you can interpret this differently as follows: solving bi-level optimisation is at least as hard as solving ILP with strict constraints. In other words, this approach works for modeling the problem, but it probably isn't very useful for actually solving the problem. $\endgroup$ – Discrete lizard Jun 17 at 13:07
  • $\begingroup$ @Discrete lizard If all we want to do is "model" the problem, we can use the "floor" function, which exactly models the floor function. It is then up to the modeling language or solver how to (approximately) implement the floor function. For instance, YALMIP overloads the MATLAB floor function yalmip.github.io/command/floor , so that takes care of the (exact) "modeling". YALMIP uses mixed integer to convert this to the problem provided to the solver, which of course is not exact. $\endgroup$ – Mark L. Stone Jun 17 at 14:26
5
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Fair point re: the practical solver, but I like this clever trick $\endgroup$ – David M. Jun 17 at 17:10
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Floating point numbers are not rational. In particular, rationals allow for exact operations, which can be implemented as long as you can represent large enough integers, while floating points are not exact. It is correct that floating points have finite precision, but they are not rationals. $\endgroup$ – Discrete lizard Jun 18 at 13:35
  • $\begingroup$ Maybe I should have added that by "floating point numbers" I mean floats according to IEEE754. Any number re-presentable by a float or double in your favorite programming language is rational. $\endgroup$ – Michael Feldmeier Jun 18 at 14:03
  • 1
    $\begingroup$ Seems like another clever trick, although at the cost of new kinds of unpleasantness. $\endgroup$ – LarrySnyder610 Jun 18 at 20:45
  • 1
    $\begingroup$ @MichaelFeldmeier Hmm. While I would agree that floats (IEEE754 or not) themselves can be equally well considered to be an implementation for rationals as for reals, I personally would expect exact representation and arithmetic when people talk about 'rationals', though. Still, this is only a digression, it doesn't really matter for this answer whether floats are rational or not. $\endgroup$ – Discrete lizard Jun 19 at 5:16
3
$\begingroup$

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

$\endgroup$
  • 8
    $\begingroup$ With the "strictly less than" constraint you'll run into problems when implementing this in a real model to be solved with a solver. You'll then have to do the epsilon trick that was already mentioned in the question. $\endgroup$ – JakobS Jun 14 at 8:44
  • $\begingroup$ $x-1 +\epsilon \leq y \leq x\implies y \leq x \leq y+1-\epsilon\implies0\leq x-y \leq1-\epsilon$. The same argument as the above answer, working for solvers, @Jakob. $\endgroup$ – Majid Jun 14 at 13:38
  • $\begingroup$ If $x=1-\epsilon$ then $y=0$ is not correct? $\endgroup$ – Majid Jun 14 at 13:50
  • 1
    $\begingroup$ I know that. But I'm still not convinced. Suppose $x=1-\frac{\varepsilon}{2}$ then $y$ has to be $1$ (as $1-\frac{\varepsilon}{2}>1-\varepsilon$), but it should be $0$. $\endgroup$ – JakobS Jun 14 at 14:58
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – JakobS Jun 14 at 15:00
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The constraint you mention differs from the one in the question, which is $y=\lfloor x\rfloor$. In fact, the constraint $\lceil a\rceil< b$ in this answer is equivalent to $a\leq b-1$. (perhaps you meant to write $\leq$ there) The question also asked for exact methods to deal with this problem, not some finite tolerance (here $0.001$). $\endgroup$ – Discrete lizard Jun 16 at 18:26
  • $\begingroup$ No, follow the link; it is transcribed correctly. $\endgroup$ – Rob Jun 16 at 18:37
  • 1
    $\begingroup$ I see. Then your linked source is incorrect. I've noted it on their answer on math.se Also, first be sure to indicate verbatim copied text with a quote block, so that we can see what text is yours and what is written elsewhere. $\endgroup$ – Discrete lizard Jun 16 at 19:10
  • 2
    $\begingroup$ @Rob I agree with DL, in that the question (and my bounty) are looking for an exact method that doesn't require a finite tolerance. Otherwise, I think your approach is similar to the one in the OP and in the answer by Majid Salavati-Khoshghalb. (Somewhat different formulation, but same basic idea.) $\endgroup$ – LarrySnyder610 Jun 16 at 20:04
  • 1
    $\begingroup$ @Rob After discussion on that post, it turns out that my above claim that $a\leq b-1$ would work is incorrect. The point about the tolerance still remains, as LarrySnyder610 also notes. $\endgroup$ – Discrete lizard Jun 16 at 21:15
1
$\begingroup$

Define $y=\lfloor{x}\rfloor$ and also define $U \in \mathbb{Z}$ and $L \in \mathbb{Z}$ as two integers that satisfy the following constraints:

$$\begin{alignat}{2}x &\leq U\tag1\\L &\leq x\tag2\end{alignat}$$

Also, define $M = U-L$ which will be a binary variable as follows:

$$M=\left\{\begin{array}{l} 0 & \text{when}\ \ x \in \mathbb{Z} \\1 & \text{otherwise}\end{array}\right.$$

The necessary constraints for the above definition are as follows:

$$\begin{alignat}{2}M &\leq U-L\tag3\\M &\geq U-L\tag4\end{alignat}$$

Now you can add the following constraint to the model:

$$x-1+(1-M) \leq y \leq x\tag5$$

Now $(1)$ through $(5)$ can be added to the constraint and in minimization problems, $M$ and in maximization problems $-M$ needs to be added to the objective function. Then in the optimal solution, if $x$ is an integer, nothing needs to be done otherwise, for $\min$ problems reduce objective function by $1$ and for $\max$ increase it by $1$.

$\endgroup$
  • $\begingroup$ But then how do you define $M$? I mean, you defined it algebraically, but you will need constraints that enforce that definition. How do you write those constraints? $\endgroup$ – LarrySnyder610 Jun 17 at 14:39
  • $\begingroup$ $M \leq U-L$ and $M \geq U-L$ $\endgroup$ – Oguz Toragay Jun 17 at 14:43
  • 1
    $\begingroup$ In my first comment, I should have said: you define $M = U-L$, but how do you enforce (or know) that $M=0$ when $x\in \mathbb{Z}$ and 1 otherwise? $\endgroup$ – LarrySnyder610 Jun 17 at 14:49
  • 1
    $\begingroup$ I agree with @Discretelizard ; that’s what I was trying to say in my comments above. Putting $M$ in the objective might coax the solution away from $y=3$ in the case of $x=4$, but might not—what if there is already a term like $1000y$ in the objective? Then the model will want $y=3$, not $y=4$, if it has the choice. $\endgroup$ – LarrySnyder610 Jun 17 at 16:00
  • 1
    $\begingroup$ Your current definition of $M$ requires testing for $x\notin \mathbb{Z}$, which is as hard to express as a floor function, see my answer here or my follow-up question. However, you do seem to describe how to deal with this in a solver, although I do not know whether this actually works. $\endgroup$ – Discrete lizard Jun 17 at 16:02
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Unfortunately I don't think this works either. $M$ could easily be large enough to force $x$ itself to be an integer, when it's not optimal (in the original problem) to do so. Example: $\min -x\ \text{s.t.}\ \lfloor x\rfloor \le 1,\ x\le 1.8$. Optimal solution is $x^*=1.8$ with objective $-1.8$. Your reformulation is: $\min -x + Ms\ \text{s.t.}\ y \le 1,\ x\le 1.8,\ y+s=x$. For sufficiently large $M$, optimal solution is $x^*=y^*=1$, $s^*=0$, objective $-1$. $\endgroup$ – LarrySnyder610 Jun 19 at 13:31
  • $\begingroup$ And I don't think there's any way to set $M$ correctly a priori so we can be sure that the model will first optimize the "real" objective and then ensure that $s$ is as small as possible. $\endgroup$ – LarrySnyder610 Jun 19 at 13:33
  • $\begingroup$ Agree, what if I set:$\min -x -M_1x-M_2y+ Ms\ \text{s.t.}\ y \le 1,\ x\le 1.8,\ y+s=x$, what is the optimal solution considering $ M_1,M_2 \ge \ge M$ ? $\endgroup$ – Majid Jun 19 at 13:51
  • $\begingroup$ @LarrySnyder610 Correction: $M_1,M_2>>M $ $\endgroup$ – Majid Jun 19 at 13:59
  • $\begingroup$ That might work in the specific case of my example (I haven't checked) but in general there is not (as far as I know) a way to set the coefficients in general that will ensure it works. Think about it this way: By adding a penalty $Ms$, you are essentially relaxing the constraint $s=0$ with a Lagrangian multiplier $M$. When you do so, you can't identify the optimal $M$ a priori; you'd need to use KKT conditions or an optimization over $M$, etc. $\endgroup$ – LarrySnyder610 Jun 19 at 14:23

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.