# Linear program with ceiling or floor functions

Is it possible to solve a linear program where constraints have ceiling or floor functions applied to variables (with maybe some constants)? For instance: $$\lceil (x_1 + a)/b \rceil + \lceil (x_2 + c)/d \rceil \leq e,$$

where $x_1$ and $x_2$ are integers. The constants as well.

Where can we find examples?

Thank you very much.

• Such a constraint will typically yield a non-convex feasible space (for example, look at $a=c=0$, $b=d=1$, and $e=3$). So I doubt linear programming will work smoothly. Jul 18 '16 at 6:50
• @GregMartin Thanks Greg. I admit that I don't understand in what the space is not convex. I'm a beginner in linear programming. If linear programming is not appropriate, what method I have to use? Jul 18 '16 at 14:18
• With floor and ceiling functions your space is a set of points. It is clear that just two points do not form a convex set , as all the points between these two points are not part of the set. You can use integer linear programming. Jul 18 '16 at 15:20
• In terms of understanding why the set of points satisfying the constraint (say) $\lceil x \rceil + \lceil x \rceil \le 3$, I recommend actually graphing that set of points. Being able to do so is a prerequisite for studying the question you originally asked, and will be enlightening as well. Jul 18 '16 at 17:28

A floor function $y=\lfloor x\rfloor$ can be formulated as:
Similarly for the ceiling $y=\lceil x \rceil$:
$y$ should have appropriate bounds (e.g. you may need to allow negative $y$). Of course for an integer variable you need a MIP solver and not just an LP solver.