creating binary variables with specific indices from subset of nodepairs (edges)
回答済み
Hello!
Im an quite new to Python/Gurobi and currently I am struggeling with creating binary decision variables for the choice of an edge in a path planning problem, regarding their indexing.
I created a small exampe 6x6 grid of obstacle free and obstacle cells. Each cell in this grid was given a number 1 to 36. Only those cells that are obstacle free are saved in the set of nodes V.
I understand that if I wanted to create a set of all possible edges between nodes in V I would write something that is equal to:
n = len(V)
x = Model.addVars(n,n,m, vtype = 'B', name = 'x')
Now in my case to ensure the avoidance of obstacles, only connections/ edges between neigbouring obstacle free cells are allowed and saved in a set of edges E - a subset of edges so to speak.
E = [ [3, 9], [9, 3], [3, 4], [4, 3],....]
To create binary variables with matching indices to the allowed node-pair edges I tried something like this, but I am not sure if this is possible.
for i in E:
e = Model.addVar(i[0], i[1], vtype = 'B', name = 'e'+str(i[0])+'_'+str(i[1]))
I need to be able to adress the first and second index (= first and second cell) of a binaryvariable of each edge in other constraints later on.
I hope I described my problem in an understandable way and am thankful for any help on my issue.
Thanks in advance and best regards,
Sophia
-
Hi Sophia,
You can construct your edge variables in different ways. One way would be to use a \(\texttt{for}\)-loop and the addVar method, e.g.,
import gurobipy as gp
m = gp.Model("test")
E = [[0,1],[1,2],[2,3]]
e = {}
for i in E:
e[(i[0],i[1])] = m.addVar(vtype='B', name='e%d%d'%(i[0],i[1]))
m.update()
# access variables via e[0,1], e[1,2], e[2,3]
print(e[0,1])or by using the addVars method
import gurobipy as gp
m = gp.Model("test")
E = [(0,1),(1,2),(2,3)]
e = m.addVars(E,vtype='B', name='e')
m.update()
print(e[0,1])
print(e[1,2])Note that in the latter case, the entries of \(\texttt{E}\) are tuples and not lists of length 2. If you cannot change your current code to generate tuples instead of lists of length 2, you can execute
E = [[0,1],[1,2],[2,3]]
E = [tuple(i) for i in E]which will turn each of the lists \(\texttt{[0,1],...}\) into tuples \(\texttt{(0,1),...}\)
Best regards,
Jaromił0 -
Hi Jaromił,
thank you for helping me with this issue. I constructed my variables as you suggested first using the for loop and it works fine.
Now I am struggeling with another issue concerning one of my constraints :
I created another variable v:
v = {}
for i in edges:
v[(i[0],i[1])] = Model.addVar(vtype = 'I', name = 'v'+str(i[0])+'_'+str(i[1]))Model.addConstr((gp.quicksum(e[edges[ij]] * d[ij] / v[edges[ij]] for ij in range(len(edges))) <= W * m - T), name = 'constraint 5')
Since v[edges[ij]] is a decision variable not a constant i get the following Gurobi Error:
'"GurobiError: Divisor must be a constant"
Could you give me a hint on how to handle/ solve this problem? Thanks again for your helpt
Best regards,
Sophia
0 -
Hi Sophia,
The Knowledge Base article How do I divide by a variable in Gurobi? holds the answer you seek.
Best regards,
Jaromił0 -
Hi Jaromił,
yes, thank you, thats exactly what I am looking for. I tried to follow the lead of your recommended article but still am making some mistake I cannot seem to solve by myself.
v = {}
for i in edges:
v[(i[0],i[1])] = Model.addVar(vtype = 'I', name = 'v'+str(i[0])+'_'+str(i[1]))
#introduction continuous variable z
z = Model.addVar(vtype = 'C', name = 'z')
#adding constraint v*z = 1
for ij in range(len(edges)):
Model.addConstr(z * v[edges[ij]] == 1)
Model.addConstr((gp.quicksum(e[edges[ij]] * d[ij] /z for ij in range(len(edges))) <= W * m - T))I still get the same Gurobi Error that my Divisor must be a constant (which makes sense, since z is a decision variable, just as v)? Did I misunderstand the article?
Sorry to bother again..
Best regards,
Sophia
0 -
Hi Sophia,
Note that by introducing the constraint \(z \cdot v_{ij} =1\) it holds that \(z=\frac{1}{v_{ij}}\). Thus, your constraint should read
Model.addConstr((gp.quicksum(e[edges[ij]] * d[ij] * z for ij in range(len(edges))) <= W * m - T))
Please note that currently you introduced exactly 1 auxiliary variable \(z\) to represent all divisions by each \(v_{ij}\). However, you should introduce an auxiliary variable \(z\) for each variable \(v_{ij}\)
v = {}
z = {}
for i in edges:
v[(i[0],i[1])] = Model.addVar(vtype = 'I', name = 'v'+str(i[0])+'_'+str(i[1]))
z[(i[0],i[1])] = Model.addVar(vtype = 'I', name = 'z'+str(i[0])+'_'+str(i[1]))
#adding constraint v*z = 1
for ij in range(len(edges)):
Model.addConstr(z[edges[ij]] * v[edges[ij]] == 1)
Model.addConstr((gp.quicksum(e[edges[ij]] * d[ij] * z[ij] for ij in range(len(edges))) <= W * m - T))If the variables \(\texttt{e}\) and \(\texttt{d}\) are both optimization variables, then you will have to introduce additional auxiliary variable to deal with the trilinear term, cf. How do I model multilinear terms in Gurobi? If only one of the variables \(\texttt{e}\) and \(\texttt{d}\) is an optimization variable, then you very likely have to set the parameter NonConvex=2, since your model is nonconvex.
Model.setParam("NonConvex",2)Best regards,
Jaromił0 -
Hi Jaromił,
thank you very much for your help! I implemented the necessary auxiliary variables as you suggested and set my parameter to NonConvex = 2 as well. I works just fine now!
Thank you for your time!
Best regards, Sophia
0
サインインしてコメントを残してください。
コメント
6件のコメント