In my linear program, I have an inequality constraint as follows.
$$ x + \frac{y}{g(z)} \leq c $$ where $x \in \mathbf{R}^+, y \in \{0, 1\}$, and $g(z)$ is a function of $z \in \mathbf{Z}_{\geq 0}$ and $ a \leq g(z) \leq b $. Here $x, y$ and $z$ are optimization variables.
I would like to linearize this constraint.
So my question is:
Can I replace $\frac{1}{g(z)}$ with another continuous variable $\frac{1}{b} \leq z' \leq \frac{1}{a}$, and use the big-M method to linearize this product?
Note that $g(z)$ cannot be zero due to the problem specifics, and $a, b \geq 0$.
Best Answer
You have $x\leq c$ when $y=0$ and $x + \frac{1}{g(x)} \leq c$ when $y=1$.
Let $U$ be an upper bound on $z$. Introduce $U+1$ binaries $\delta_i$ to represent which value $z$ has, $z = \sum_{i = 0}^U \delta_i i$ where $\sum_{i = 0}^U \delta_i = 1$. The complicating term can now be expressed linearly as $\sum_{i=0}^N \delta_i \frac{1}{g(i)}$
The logics for selecting constraint with $y$ is standard big-M modelling, and you end up with
$$ x \leq c + My,~x + \sum_{i=0}^U \frac{\delta_i}{g(i)} \leq c + M(1-y), ~z = \sum_{i = 0}^U \delta_i i,~\sum_{i=0}^U \delta_i = 1$$