How to constrain MILP to allow only one agent in an area at a time

Awaiting user input

Sydney Dolan

November 01, 2021 16:32

• 
• 

Hello,

I'm am using an MILP for path planning. Presently, I have the obstacles coded as

for (Ao, bo) in O:
flags = problem.addVars(len(Ao), vtype=GRB.BINARY)
problem.addConstr(flags.sum() <= len(Ao) - 1)
for row in range(len(Ao)):
b = bo[row] + linalg.norm(Ao[row]) * r
problem.addConstr(LinExpr(Ao[row], p1) + 1e5 * flags[row] >= b)
problem.addConstr(LinExpr(Ao[row], p2) + 1e5 * flags[row] >= b)

 

where O represents the list of obstacles on the plot, and p1 and p2 represent the x and y coordinates of the agents position. I thought I could implement a similar constraint to limit the amount of agents in a region. Where a flag would be used to identify if the agent was in the region, and there was only 1 flag allowed at a time.

inregion = problem.addVars(agents_num,N, vtype=GRB.BINARY)

for i in range(N):
problem.addConstr((gurobipy.quicksum(inregion[j,i] for j in range(agents_num))) <= 1) #agents_num)

# Add the constraints to avoid the obstacles
for idx in range(agents_num):
for n in range(N):
p1 = [vars['(A%sN%sD%s)' % (idx, n, k)] for k in range(dim)]
p2 = [vars['(A%sN%sD%s)' % (idx, n+1, k)] for k in range(dim)]
for (Ao, bo) in O: # O represents desired region
flags = problem.addVars(len(Ao), vtype=GRB.BINARY)
problem.addConstr(flags.sum() - 4 - inregion[idx,n] <= -1)
for row in range(len(Ao)):
b = bo[row] + linalg.norm(Ao[row]) * r
problem.addConstr( (LinExpr(Ao[row], p1) + 1e5 * flags[row]) >= b)
problem.addConstr( (LinExpr(Ao[row], p2) + 1e5 * flags[row]) >= b)

But this constraint doesn't seem to have any effect on the resultant model problem. Do you have any advice about how would go about implementing this constraint?  Thanks in advance.

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  June 23, 2025 02:45 Edited

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Maliheh Aramon

  • Gurobi Staff

  November 05, 2021 06:44 Edited

  Hi Sydney, 

  Could you please help me to better understand your question? You mentioned that you would like to add a constraint such that at most one agent is assigned to an area. Your constraint below defined over inregion binary decision variables guarantees that at most one agent is assigned to each region.

  problem.addConstr((gurobipy.quicksum(inregion[j,i] for j in range(agents_num))) <= 1) #agents_num)

  I am not sure which constraint does not work as you expect.

  It would be great if you could share a minimal reproducible working example of the issue you are describing above.

  Best regards,

  Maliheh

   

  0

Post is closed for comments.