2

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

KGM
  • 2,265
  • 7
  • 23
  • Is $||\mathcal{C}_u||=0$ permitted? – RobPratt Sep 10 '20 at 00:41
  • @RobPratt, No, its not! Does it affect your current formulation? – KGM Sep 10 '20 at 07:24
  • 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$? – RobPratt Sep 10 '20 at 12:59
  • @RobPratt, yes I want $x_{t,u}=1$. – KGM Sep 10 '20 at 17:57
  • 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. – RobPratt Sep 10 '20 at 18:58

1 Answers1

4

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

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • Is it possible a formulate a heuristic solution to this problem? – KGM Sep 12 '20 at 13:01
  • @dipaknarayanan I added an indirect approach that is heuristic if you stop early. – RobPratt Sep 12 '20 at 14:50
  • Thanks a lot. By the way what do you mean by "that is heuristic if you stop early"? – KGM Sep 16 '20 at 11:33
  • 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. – RobPratt Sep 16 '20 at 12:50
  • 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...https://or.stackexchange.com/questions/4858/how-can-i-linearize-this-if-then-constraint?noredirect=1#comment8224_4858 – KGM Sep 16 '20 at 15:48
  • Also, when I perform linearization of the multiplications of continuous and integer variable, I believe we need to make use of Big-M approach. What would be the ideal value for M? Is it the $U$ in your bisection search proposal? – KGM Sep 16 '20 at 15:53
  • Yes, $z \le U$, so you can use $U$ as big-M when you linearize $z x_{t,u}$. – RobPratt Sep 16 '20 at 16:28