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

ユーザーの入力を待っています。

Sydney Dolan

2021年11月01日 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

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年06月23日 02:45 編集済み

  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

  2021年11月05日 06:44 編集済み

  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

投稿コメントは受け付けていません。