# Help modeling grid placement problem

I'm trying to model a grid placement problem to exercise in OR.

The problem is defined as:

• a grid of some dimension (let's say 500x500)
• N users that need connection. Every user has:
• a defined position on the grid
• a speed value
• a latency value
• M wifi access points to place on the grid. Every access point has:
• a range
• a speed value

Objective is to maximize: $$\sum_{n \in N} user\_score(n)$$ given $$user\_score(n) = \max_{m \in M} score(n, m)$$ $$score(n, m) = \begin{cases} speed(n) * speed(m) - latency(n) * distance(n,m) & distance(n,m) <= range(m)\\ 0 & distance(n,m) > range(m) \end{cases}$$ $$distance(n,m) = abs(n_x - m_x) + abs(n_y - m_y) \space\space\text{(manhattan distance)}$$

• two access points can't share the same location on the grid
• an access point and a user can share the same location
• if no access point is in range, user score is 0

I tried modeling it as follows, using or-tools:

model = cp.CpModel()

all_x = []
all_y = []
all_k = []

for a in access_points:
x = model.NewIntVar(0, grid_w - 1, f'x_{a.id}')
y = model.NewIntVar(0, grid_h - 1, f'y_{a.id}')
k = model.NewIntVar(0, (grid_w - 1) * 1000 + grid_h, f'k_{a.id}')

model.Add(k == x * 1000 + y)

all_x.append(x)
all_y.append(y)
all_k.append(k)

scores = []
for b in users

u_score = model.NewIntVar(0, cp.INT32_MAX, f'u_score_{b.id}')
all_u_scores = []

for ia, a in enumerate(access_points):

abs_x = model.NewIntVar(0, grid_w, f'abs_x_{b.id}_{a.id}')
abs_y = model.NewIntVar(0, grid_h, f'abs_y_{b.id}_{a.id}')

in_range = model.NewBoolVar(f'in_range_{b.id}_{a.id}')

score = model.NewIntVar(0, cp.INT32_MAX, f'score_{b.id}_{a.id}')
model.Add(score == a.speed * b.speed - b.latency * (abs_x + abs_y)).OnlyEnforceIf(in_range)

all_b_scores.append(score)

scores.append(b_score)

model.Maximize(sum(scores))


This works well with a small grid with a few users/access points, but scales bad on bigger problem instances.

Is the model good? Any better way to model the problem?

• This looks like a facility location problem. Mar 3, 2022 at 14:26

Let $$x_{ij}^p$$ be a binary variable that indicates if user $$i\in I$$ is assigned to access point $$j \in J = \{1,...,M\}$$ located in position $$p\in P$$, and let $$z_{j}^p$$ be a binary variable that indicates if access point $$j\in J$$ is assigned to position $$p\in P$$.

For every tuple $$(i,j,p) \in I \times J \times P$$, a score $$c_{ij}^p$$ is computed according OP's rules: $$c_{ij}^p = \begin{cases} 0 & \mbox{ if } d_{ip} > \mbox{range}(j) \\ \mbox{speed}(i)\cdot\mbox{speed}(j)- \mbox{latency}(i)\cdot d_{ip}& \mbox{ otherwise } \end{cases}$$

You want to maximize the total score: $$\max \; \sum_i\sum_j\sum_p c_{ij}^p x_{ij}^p$$ subject to

• assign users to access points: $$\sum_j\sum_p x_{ij}^p = 1 \quad \forall i \in I$$

• each access point has a unique position: $$\sum_p z_{j}^p = 1 \quad \forall j \in J$$

• each position has at most one access point: $$\sum_j z_{j}^p \le 1 \quad \forall p \in P$$

• consistency between $$x_{ij}^p$$ and $$z_{j}^p$$: $$x_{ij}^p \le z_{j}^p \quad \forall i \in I, \forall j \in J, \forall p \in P$$

You might want to consider maximizing the minimum score.

My simulations with some random data (possibly poorly randomized and scaled) yield the following output: • Thanks for the reply. If i understood correctly, I should have an $y_j$ variable for each grid position for each access point. Additionally, each user should be linked to each of these access point positions by $X_{ij}$ This means that I woud have, given an $N \times M$ grid with $I$ users and $J$ access points, $N \times M \times I \times J$ variables $x_{ij}$. Is that correct? Mar 3, 2022 at 21:42
• Not exactly. If you have an $N\times M$ grid, then $J=N \times M$, so you would have $I\times N \times M$ $x$ variables. That said, you may not have to define them all. You could define only the ones for which the score is positive, and see if it is feasible. Mar 4, 2022 at 8:46
• I'm missing something. Every position in the grid can contain any of the access points, that have different ranges. So $c_{ij}$ can't be defined if $j \in J$ with $J = N \times M$, because $range(j)$ is not known as it depends on the range of the access point placed at $j$ Mar 4, 2022 at 20:00
• OK, i see. I have edited accordingly. Mar 5, 2022 at 0:45