0
$\begingroup$

I don't know how to solve this equation,

$$\left\lceil\frac{x-A}{B}\right\rceil C + D x < E, \quad x\in \mathbb{Z}$$

In this equation, only $x$ is unknown and $x$ is integer, but $A,B,C,D,E$ are maybe decimals and they are greater than zero. How can I get the upper bound of $x$?

$\endgroup$
1
$\begingroup$

Introduce an integer variable $y$ and a continuous variable $s$, and write: $$\begin{align} & y C + Dx \le E\\ &y = \frac{x-A}{B} + s \\ &s \in [0,0.999] \\ &y \in \{...,-3,-2,-1,0,1,2,3,...\} \end{align}$$ Of course a $<$ constraint is no good, so I made it a $\le$ constraint.

$\endgroup$
6
  • $\begingroup$ You should have asked whether the strict inequality is intended, because it changes the answer: $\lceil a\rceil < b$ is equivalent to $a \leq b-1$, which means that the slack variable is unnecessary. In other words, you have answered a slightly different question than what was asked. $\endgroup$ – Discrete lizard Jun 16 '19 at 19:09
  • $\begingroup$ Claim $\lceil a \rceil < b \Rightarrow a \le b-1$. Counter example: $b=1.5$ $\endgroup$ – Erwin Kalvelagen Jun 16 '19 at 20:36
  • $\begingroup$ Ah, yes, I was confused. That only works if $b$ is integral. Otherwise we have $a \leq\lfloor b\rfloor$, but that only works when $b$ is not integral. So that doesn't help, as checking for integrality is at least as hard as modeling a strict inequality. Fair enough. I do think that replacing the strict inequality by a non-strict one deserves an argument, though. $\endgroup$ – Discrete lizard Jun 16 '19 at 21:03
  • $\begingroup$ I don't think so. In optimization, we should never use $<$ except if everything in the constraint is 100% integer valued. I think you are just confusing the issue more than being helpful. $\endgroup$ – Erwin Kalvelagen Jun 16 '19 at 21:07
  • $\begingroup$ Yes, but I think at least mentioning why would be helpful in this context. $\endgroup$ – Discrete lizard Jun 16 '19 at 21:18

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.