creating binary variables with specific indices from subset of nodepairs (edges)
AnsweredHello!
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
-
Official comment
-
Gurobi Staff
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 try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
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 -
Post is closed for comments.
Comments
7 comments