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 Answer 1

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$ Jun 16, 2019 at 19:09
  • $\begingroup$ Claim $\lceil a \rceil < b \Rightarrow a \le b-1$. Counter example: $b=1.5$ $\endgroup$ Jun 16, 2019 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$ Jun 16, 2019 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$ Jun 16, 2019 at 21:07
  • $\begingroup$ Yes, but I think at least mentioning why would be helpful in this context. $\endgroup$ Jun 16, 2019 at 21:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .