Is my formulation correct and how to formulate this IF-THEN constraint?

Question

I have system with $N_U$ users and $N_T$ transmitters. Multiple transmitters can transmit to a single users and one transmitter can transmit to many users, i.e., two sets of transmitters serving two different users can have one or more common transmitters.

When a transmitter does not transmit to a given user, it acts an an interferer to the given user, i.e., its transmission deteriorates the overall signal quality.

I want to maximum the minimum of all users' signal qualities. The formulation I created like this

$$\max \hspace{2mm}\min_{u=1,\cdots,N_{U}}\hspace{2mm}Q_u$$
$$\text{subject to}$$ $$Q_u=\frac{\sum_{t\in \mathcal{C}_u}P_{t,u}}{\sum_{t\notin \mathcal{C}_u,t\in\mathcal{T}}P_{t,u}+\sigma}$$
$$||\mathcal{C}_u||\le 5, \forall u$$\

Here, $\mathcal{T}$ is the set of all the transmitters, $\mathcal{C}_u$ is the set of transmitters serving user $u$. $P_{t,u}$ is the transmission power from transmitter $t$ to user $u$. $\sigma$ is a known parameter. $Q_u$ is the quality of user $u$.$||\mathcal{C}_u||$ is the cardinality of set $\mathcal{C}_u$. $P_{t,u}$ is a known value. So, the optimization is all about finding the set $\mathcal{C}_u, u=1,\cdots, N_U$.

Answer 1

Introduce a variable $z$ to represent $\min_u Q_u$ in the objective, and let binary variable $x_{t,u}$ indicate whether transmitter $t$ serves user $u$. Then replace $||\mathcal{C}_u||$ with $\sum_{t\in T} x_{t,u}$ throughout. Also $\sum_{t\in C_u} P_{t,u}$ becomes $\sum_{t\in T} P_{t,u} x_{t,u}$, and $\sum_{t\notin C_u} P_{t,u}$ becomes $\sum_{t\in T} P_{t,u} (1-x_{t,u})$.

To linearize the $$z \le \frac{\sum_{t\in T} P_{t,u} x_{t,u}}{\sum_{t\in T} P_{t,u} (1-x_{t,u})+\sigma}$$ constraints, multiply both sides by the denominator and perform the usual linearization of the product of a binary variable and a continuous variable.

Assuming $\alpha$ is a constant, the if-then logic is just fixing variables. If $P_{t,u} \ge \alpha$, then fix $x_{t,u}=1$ and fix $x_{t',u}=0$ for all $t'\not=t$.

---

Here's an indirect approach that avoids products of decision variables. We want to maximize $z$ subject to \begin{align} \left(\sum_{t\in T} P_{t,u} (1-x_{t,u})+\sigma\right) z &\le \sum_{t\in T} P_{t,u} x_{t,u} && \text{for all $u$} \\ 1 \le \sum_{t\in T} x_{t,u} &\le 5 && \text{for all $u$} \\ x_{t,u} &= 1 && \text{for all $t,u$ such that $P_{t,u} \ge \alpha$}\\ x_{t',u} &= 0 && \text{for all $t,u$ such that $P_{t,u} \ge \alpha$ and $t'\not= t$} \\ x_{t,u} &\in\{0,1\} && \text{for all $t,u$} \end{align} For fixed $z=\hat{z}$, this problem is linear. Furthermore, if the problem is feasible for $z=\hat{z}$, then it is feasible for all $z \le \hat{z}$. Similarly, if the problem is infeasible for $z=\hat{z}$, then it is infeasible for all $z \ge \hat{z}$. So apply a bisection search to find the optimal $z$. For an initial interval $[L,U]$, you can take $L=0$ and $U=\min_u\left(\sum_{t\in T} P_{t,u}\right)/\sigma$.