0
$\begingroup$

I have a system with $S$ service points. There are also $U$ users in the system.

We have $$U>S>G$$

One group can have maximum $M$ service points, but there is no restrictions on the number of users per group.

A user is served by all the service points belonging to the user's group/cluster. Therefore, if one user happens to be in a group of multiple service points, then it will be served by all the service points in that group. Also, the service points in one group negatively impact the service offered to a user in a different group.

There is a gain between a service point and a user, denoted by $h_{u,s}, u=1,2,\cdots,U, s=1,2,\cdots,S$.

The objective is to maximise the sum-quality of all the users in the system

$$\max\sum_{u=1}^Uq_u$$

How can I mathematically formulate this optimization problem? How to express the constraints mathematically?

Thoughts

A similar equation is given here. How to transform this problem with logarithmic objective function into an approximated convex optimization problem?

The solution suggested there does not help. It is helpful to convexity my objective may be. But my question is different here. I want to have a mathematical formulation. In the previous problem, we had only user and service points lets ay. But in this problem, we have grouping of service points and users, which make the formation difficult.

EDIT:

For linearising constraint (5) in the above formulation, let, $\nu_{u,s,g}=y_{u,g}z_{s,g}$. Then I follow what @RobPratt suggests.

Improve this question
$\endgroup$
5
  • $\begingroup$ Does this answer your question? How can I convexify (allowed some approximation) the objective function? $\endgroup$
    – RobPratt
    Mar 30, 2021 at 20:54
  • $\begingroup$ @RobPratt, No. I think it is a different problem. $\endgroup$
    – KGM
    Mar 30, 2021 at 21:03
  • $\begingroup$ OK, I saw that you want to maximize a ratio of linear functions, and the Charnes-Cooper transformation still applies. How does $h_{u,s}$ relate to the other variables here? Also, I recommend avoiding two set of $x$ variables; rename one of them, say to $y$. $\endgroup$
    – RobPratt
    Mar 30, 2021 at 21:14
  • $\begingroup$ @RobPratt, I have edited the objective. But I do not how how to do mapping between groups and users and service points. $\endgroup$
    – KGM
    Mar 30, 2021 at 21:25
  • $\begingroup$ I am starting to understand what you want to do, but please take another pass at editing. For example, you defined $\mathcal{S}_g$ three times and then didn’t use it anywhere. Also, please use a different symbol for $\mathcal{S}_u$ to avoid ambiguity. $\endgroup$
    – RobPratt
    Mar 31, 2021 at 2:51

1 Answer 1

Reset to default
5
$\begingroup$

With the natural binary decision variables $x_{s,u}$, $y_{u,g}$, and $z_{s,g}$ you had defined earlier, the problem is to maximize $\sum_u q_u$ subject to \begin{align} q_u &= \frac{\sum_s h_{s,u} x_{s,u}}{\sum_s h_{s,u} (1-x_{s,u})} &&\text{for all $u$} \tag1 \\ \sum_g y_{u,g} &= 1 &&\text{for all $u$} \tag2 \\ \sum_g z_{s,g} &= 1 &&\text{for all $s$} \tag3 \\ \sum_s z_{s,g} &\le M &&\text{for all $g$} \tag4 \\ x_{s,u} &= \sum_g y_{u,g} z_{s,g} &&\text{for all $s,u$} \tag5 \end{align} You can linearize $(1)$ by using a Charnes-Cooper transformation, as described here. You can linearize the product in $(5)$ in the usual way, as described here.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for the answer. What additional constraints I should have if the number of groups is also a variable. It is not a fixed/known parameter anymore. $\endgroup$
    – KGM
    Apr 21, 2021 at 14:15
  • $\begingroup$ Please see my edit for the Linearization I used to linearise constraint (5). Am I doing it right? The indexing are sometimes confusing me. $\endgroup$
    – KGM
    Apr 21, 2021 at 14:30
  • $\begingroup$ Yes, you did it correctly. I had an error in (5) but corrected it now. You will need $x_{s,u}=\sum_g \nu_{u,s,g}$ along with your three new linearization constraints. $\endgroup$
    – RobPratt
    Apr 21, 2021 at 16:15
  • $\begingroup$ thanks for the correction. What about if I want to have the number of groups as an optimization variable, i.e., let the optimiser decide the optimal number of groups which is $\le G$. How can I enforce such requirements $\endgroup$
    – KGM
    Apr 21, 2021 at 17:43
  • $\begingroup$ Nothing in the current model forces all groups to be used, so no change is needed. $\endgroup$
    – RobPratt
    Apr 21, 2021 at 18:04

Your Answer

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

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