2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is $||\mathcal{C}_u||=0$ permitted? $\endgroup$ – RobPratt Sep 10 at 0:41
  • $\begingroup$ @RobPratt, No, its not! Does it affect your current formulation? $\endgroup$ – dipak narayanan Sep 10 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 Sep 10 at 12:59
  • $\begingroup$ @RobPratt, yes I want $x_{t,u}=1$. $\endgroup$ – dipak narayanan Sep 10 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 Sep 10 at 18:58
3
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Is it possible a formulate a heuristic solution to this problem? $\endgroup$ – dipak narayanan Sep 12 at 13:01
  • $\begingroup$ @dipaknarayanan I added an indirect approach that is heuristic if you stop early. $\endgroup$ – RobPratt Sep 12 at 14:50
  • $\begingroup$ Thanks a lot. By the way what do you mean by "that is heuristic if you stop early"? $\endgroup$ – dipak narayanan Sep 16 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 Sep 16 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$ – dipak narayanan Sep 16 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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