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

  • $\begingroup$ Is $||\mathcal{C}_u||=0$ permitted? $\endgroup$
    – RobPratt
    Commented Sep 10, 2020 at 0:41
  • $\begingroup$ @RobPratt, No, its not! Does it affect your current formulation? $\endgroup$
    – KGM
    Commented Sep 10, 2020 at 7:24
  • $\begingroup$ To prevent $||\mathcal{C}_u||=0$, impose $\sum_t x_{t,u}\ge 1$. If $P_{t,u}\ge\alpha$, do you also want $x_{t,u}=1$? $\endgroup$
    – RobPratt
    Commented Sep 10, 2020 at 12:59
  • $\begingroup$ @RobPratt, yes I want $x_{t,u}=1$. $\endgroup$
    – KGM
    Commented Sep 10, 2020 at 17:57
  • $\begingroup$ OK, that is really just preprocessing because $P_{t,u}$ and $\alpha$ are data. You can either fix $x_{t,u}=1$ and fix $x_{t',u}=0$ for all other $t'\not= t$, or just omit those disallowed $x_{t',u}$ variables from the problem altogether. $\endgroup$
    – RobPratt
    Commented Sep 10, 2020 at 18:58

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

  • $\begingroup$ Is it possible a formulate a heuristic solution to this problem? $\endgroup$
    – KGM
    Commented Sep 12, 2020 at 13:01
  • $\begingroup$ @dipaknarayanan I added an indirect approach that is heuristic if you stop early. $\endgroup$
    – RobPratt
    Commented Sep 12, 2020 at 14:50
  • $\begingroup$ Thanks a lot. By the way what do you mean by "that is heuristic if you stop early"? $\endgroup$
    – KGM
    Commented Sep 16, 2020 at 11:33
  • $\begingroup$ Bisection search maintains an interval for $z$ where the lower bound of the interval is feasible and the upper bound is infeasible. Each step bisects the interval, and the search terminates when these two bounds are close enough. Whenever you decide to stop, you have a feasible solution and an optimality gap. $\endgroup$
    – RobPratt
    Commented Sep 16, 2020 at 12:50
  • $\begingroup$ thanks for your nice explanation. Now, I have access to MILP solver MOSEK with CVX. With CVX, we cannot do any preprocessing, I mean we cannot assign some value to some of the variables. So, I would like to express the If-then as a constraint. I have asked a new question on this...or.stackexchange.com/questions/4858/… $\endgroup$
    – KGM
    Commented Sep 16, 2020 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.