1
$\begingroup$

I am trying to solve a capacitated MCLP problem with two additional constraints.

  1. Non-overlapping circles
  2. Minimum and Maximum value for the capacity for a circle.

for 2nd constraint, I am able to add maximum limit but I am getting error when I try to add the minimum limit (as some locations are zeros and cannot be selected)

All the details are same as this question. Capacitated Maximum Coverage Location Problem, Python and Gurobi and I found it useful for adding a constraint.

Pls suggest how can I add the second constraint?

Note: Below image is added for the added query i.e not all demand points from a location, were included in the optimized solution. pls see the query in detail below.

enter image description here

enter image description here

$\endgroup$

2 Answers 2

1
$\begingroup$

So, you are looking for something like
$Minpoints\cdot x_j \le \sum_{i \in\ S_j} y_i \ \ \forall j \in\ J$
where $x_j =1$ if Facility j is selected at all, $S_j =\{i \in\ I: d_{i,j} \le r\}$ and Minpoints is a number you choose

Using same code as before

for j in J:
 model.addConstr(minpoints*x[j] <= quicksum(y[i] for i in np.where(D[:,j]==1)[0]))
$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – TheSimpliFire
    Jan 9, 2023 at 17:21
1
$\begingroup$

Code with Sample data:\

import gurobipy as gp
from gurobipy import *
import numpy as np
from scipy.spatial.distance import pdist
from collections import namedtuple
from scipy.spatial import distance_matrix as dm

N =15 #Sites" Towers
R = 86
#Generate Data
Points = namedtuple('Points', 'x, y')
def gen_data(Points,N):
  locations = []
  for p in range(N):
    x,y = np.random.uniform(1,10,size = 2)
    points = Points(x,y)
    if points.x**2 + points.y**2 <= R**2:
      locations.append(points)
  return np.array([[p.x,p.y] for p in locations],dtype='float16')
  #return sites
#print(sites)
#Generate sites
sites = gen_data(Points,N)

towers = gen_data(Points,7)
#print(towers)

N,_ = sites.shape
I = [*range(N)]
T,_ = towers.shape
J = [*range(T)]
K = 5
maxpoints = 13 #per tower circle
minpoints = 2 #per tower circle
#Generate distance D(i,j)
D = dm(sites,towers).astype('float16')
print(D)
#Masking
mask = (D < 7)
D[mask] = 1; D[~mask]=0

model = Model('fac')

x = model.addVars(J,vtype='b',name='x')
y = model.addVars(I,vtype='b',name='y')

C1 = model.addConstr(x.sum() == K,'C1')
C2 = model.addConstrs((minpoints*x[j] <= quicksum(y[i] for i in np.where(D[:,j]==1)[0])\
                      for j in J),'C2')

#C3 = model.addConstrs((quicksum(x[j] for j in np.where(D[i,:]==1)[0])<= K*(1-y[i])+y[i]\
 #                     for i in I),'NonOverlapping')

                  for j in J),'C2')
C5 = model.addConstrs((maxpoints >= quicksum(y[i] for i in np.where(D[:,j]==1)[0])\
                      for j in J),'C2')    
C4 = model.addConstrs((y[i] == 1 for i in np.where(np.sum(D,axis=1)>=1)[0]),'C4')
obj = y.sum()
model.setObjective(obj,GRB.MAXIMIZE)
model.update()
model.optimize()
model.printAttr('x')
$\endgroup$
2
  • $\begingroup$ Thank you Sutanu for showing the path. In your code, y[i] ==1 seems to work for allocating all demand points. But I think the problem comes when max capacity constraint is added because it just caps inclusion beyond the max limit and then y[i] cannot be one for that demand point. I have added the max capacity constraint like this -> for j in range(J): m.addConstr(quicksum(int(a[i])*y[i] for i in np.where(D[:,j]==1)[0]) <= 32) please tweak your code. Sorry I am getting error when I am trying to add it in your code. $\endgroup$
    – Nandy
    Jan 9, 2023 at 18:43
  • $\begingroup$ Lets make it the last comment, otherwise moderator will remove. See you are not assigning any location to site like $x_{i,j}$. Here selecting demand sites & facilities are kind of independent variables. So when you are putting a max point basically you are selecting a subset of $y$ and constraining it. So if any $y_i = 1$ for one subset of $x$ it remains 1 for the other Xs, in a way restricting total number of Ys you are selecting. Otherwise you need to you 2-D variable like $x_{i,j}$ $\endgroup$ Jan 9, 2023 at 20:10

Your Answer

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

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