Wednesday, March 2, 2016

Ceiling function in a Mixed Integer Program

In this post the question was asked how to implement the Ceiling() function in a MIP model. The constraint in question is:

\[\left\lceil \frac{x-A}{B} \right\rceil \cdot C + D\cdot x < E \]

Answer:

Introduce an integer variable \(y\) and a continuous slack variable \(s\) and write:

\[\begin{align} &y\cdot C + D \cdot x \le 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 \(<\) constraints are no good, so make that \(\le\). 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\).