4
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$ Jul 18 '16 at 6:50
  • $\begingroup$ @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? $\endgroup$
    – Dingo13
    Jul 18 '16 at 14:18
  • $\begingroup$ 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. $\endgroup$
    – Kuifje
    Jul 18 '16 at 15:20
  • $\begingroup$ 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. $\endgroup$ Jul 18 '16 at 17:28
7
$\begingroup$

A floor function $y=\lfloor x\rfloor$ can be formulated as:

\begin{align} & y \> \text{integer variable}\\ & x-0.999 \le y \le x \end{align}

Similarly for the ceiling $y=\lceil x \rceil$:

\begin{align} & y \> \text{integer variable}\\ & x \le y \le x+0.999 \end{align}

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

$\endgroup$
1
  • $\begingroup$ Thanks for your answer Erwin $\endgroup$
    – Dingo13
    Jul 19 '16 at 12:23

This site is temporarily in read only mode and not accepting new answers.

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