# How to mathematically formulate the optimization problem?

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.

• Does this answer your question? How can I convexify (allowed some approximation) the objective function? – RobPratt Mar 30 at 20:54
• @RobPratt, No. I think it is a different problem. – dipak narayanan Mar 30 at 21:03
• 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$. – RobPratt Mar 30 at 21:14
• @RobPratt, I have edited the objective. But I do not how how to do mapping between groups and users and service points. – dipak narayanan Mar 30 at 21:25
• 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. – RobPratt Mar 31 at 2:51

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.
• 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. – RobPratt Apr 21 at 16:15
• 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 – dipak narayanan Apr 21 at 17:43