how to minimize the gap between a fractional linear expression with a constant value
I have a selection problem with objective function like: $$ min\mid\frac{\sum a_i\cdot x_i}{\sum b_i\cdot x_i}-\alpha\mid $$
Let me explain this objective function: we want the production efficiency as close to 50% as possible. Yes, we do not pursue max production efficiency.
As it is a selection problem, $x_i$ is binary (0 or 1). $a, b$ are constant vector and $\alpha$ is a constant scalar.
I know how to maximize a linear fractional programming problem (MILFP) via Charnes-Cooper transformation. And I know how to handle a absolute value in objective function. But I want to know how to handle a problem like that.
My solution to MILFP, inspired by Charnes-Cooper transformation and Linear-fractional_programming:
original: $$ min\frac{\sum a_i\cdot x_i}{\sum b_i\cdot x_i} $$ converted: $$ min(\sum a_i\cdot y_i) \\ st. \\ \sum b_i \cdot y_i = 1 \\ 0 <= y_i <= M \cdot x_i, \ for \ each \ i \\ y_i -t<=M\cdot(1-x[i]), \ for \ each \ i \\ y_i -t>=-M\cdot(1-x[i]), \ for \ each \ i $$ where t and y are float random variables.
My solution to absolute value in objective function:
original: $$ min\mid \sum x_i-\alpha\mid $$ converted: $$ min(z) \\ st. \\ z>=\sum x_i - \alpha \\ z>=-(\sum x_i - \alpha) $$ I wonder how to combine the two solutions together. I tried but it didnot work.
Introduce continuous decision variable $z$, with bounds $[0,M]$. To avoid the absolute value, minimize $z$ subject to \begin{align} z &\ge \frac{\sum_i a_i x_i}{\sum_i b_i x_i} - \alpha \\ z &\ge -\frac{\sum_i a_i x_i}{\sum_i b_i x_i} + \alpha \end{align} To avoid the ratios, multiply both sides by the denominator $\sum_i b_i x_i$: \begin{align} z \sum_i b_i x_i &\ge \sum_i a_i x_i - \alpha \sum_i b_i x_i \\ z \sum_i b_i x_i &\ge -\sum_i a_i x_i + \alpha \sum_i b_i x_i \end{align} To linearize the product $z x_i$, introduce continuous decision variable $y_i$ and impose linear constraints: \begin{align} \sum_i b_i y_i &\ge \sum_i (a_i - \alpha b_i) x_i \tag1\label1\\ \sum_i b_i y_i &\ge \sum_i (-a_i + \alpha b_i) x_i \tag2\label2\\ 0 \le y_i &\le M x_i &&\text{for all $i$}\tag3\label3 \\ 0 \le z - y_i &\le M (1-x_i) &&\text{for all $i$} \tag4\label4 \end{align} Now minimize $z$ subject to \eqref{1} through \eqref{4}.
Alternatively, you can replace big-M constraints \eqref{3} and \eqref{4} with indicator constraints \begin{align} x_i = 0 &\implies y_i = 0 &&\text{for all $i$} \\ x_i = 1 &\implies y_i = z &&\text{for all $i$} \end{align}
You can reduce the number of nonzero constraint coefficients by introducing a decision variable $r$ to represent the ratio and then linearizing $y_i=r x_i$: \begin{align} z&\ge r-\alpha \\ z&\ge \alpha-r \\ \sum_i b_i y_i &= \sum_i a_i x_i\\ 0 \le y_i &\le M x_i &&\text{for all $i$} \\ 0 \le r - y_i &\le M (1-x_i) &&\text{for all $i$} \end{align}