Lazy Constraints / TSP
回答済みHello,
I need to implement Lazy Constraints.
I implement TSP model (This model: http://www.opl.ufc.br/pt/post/tsp/)
But i dont know how i implement subtour in lazy constraint.
My code:
file = open('17.txt')
lines = file.readlines()
file.close()
cost_matrix = []
for i in range(len(lines)):
aux = lines[i][:-1].split('\t')
aux = [int(i) for i in aux if i!= '']
cost_matrix.append(aux)
tam = len(cost_matrix)
n = list(range(tam))
m = list(range(1, tam))
for i in range(tam):
cost_matrix[i][i] = 999999999999
import gurobipy as gp
model = gp.Model()
x = model.addVars(n, n, vtype=gp.GRB.BINARY, name="x")
u = model.addVars(n, vtype=gp.GRB.INTEGER, name="u")
model.setObjective(
gp.quicksum(x[i, j] * cost_matrix[i][j] for i in n for j in n),
sense=gp.GRB.MINIMIZE)
# R1
c1 = model.addConstrs(
gp.quicksum(x[i, j] for i in n) == 1 for j in n if (i != j))
# R2
c2 = model.addConstrs(
gp.quicksum(x[j, i] for i in n) == 1 for j in n if (i != j))
# R3 (subtour constraint)
c3 = model.addConstrs(u[i] - u[j] + tam * x[i, j] <= tam-1
for i in m
for j in n
if (i != j))
Someone can help me?
Detail, I know there is a very good model with lazy constraints, but I need a slower model to do some analysis in my PHD.
I also understand how callbacks work and I tried, based on the existing implementation, to adapt to my code but I tried in several ways and I didn't get any results, just errors.
Thanks for the help ^^
-
正式なコメント
-
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 Roberval,
I think that the tsp.py example implements exactly what you are looking for.
Detail, I know there is a very good model with lazy constraints, but I need a slower model to do some analysis in my PHD.
You could try increasing the size of the model to "slow it down".
Best regards,
Jaromił1 -
-
Thanks, I went on to add other constraints that aren't part of the classic model to get what I need.
I don't understand why I can't add this C3 in a callback like this:
def subTour(model, where):
if where == gp.GRB.Callback.MIPSOL:
model.cbLazy(u[i] - u[j] + tam * x[i, j] <= tam-1
for i in m
for j in n
if (i != j))This error appears:
TypeError Traceback (most recent call last)
src/gurobipy/callback.pxi in gurobipy.CallbackClass.callback()
<ipython-input-6-2e1575e521d5> in subtourelim(model, where) 5 if where == gp.GRB.Callback.MIPSOL: 6 model.cbLazy(u[i] - u[j] + tam * x[i, j] <= tam-1 ----> 7 for i in m 8 for j in n 9 if (i != j))
src/gurobipy/model.pxi in gurobipy.Model.cbLazy()
TypeError: unsupported operand type(s) for -: 'generator' and 'NoneType'
0 -
-
-
What is the error you get?
Note that you can't just access the model's variables and other parameters from a callback. You have to save the variables in a private object just as is done in the tsp.py example with \(\texttt{model._vars}\).
1 -
-
Where can I read about private object in gurobipy?
i read this:
https://www.gurobi.com/documentation/9.5/refman/lazyconstraints.html
https://www.gurobi.com/documentation/9.5/refman/py_model_cblazy.html
and this:
And I didn't know that, can you give me an example of how to do it or the documentation about the private objects?
0 -
-
-
And I didn't know that, can you give me an example of how to do it or the documentation about the private objects?
There is no Gurobi documentation about this, because it is a feature of the Python language. Having a closer look at the tsp.py example should be helpful.
The error
TypeError: unsupported operand type(s) for -: 'generator' and 'NoneType'
indicates that one of the used object is uninitialized, i.e., \(\texttt{None}\). If after re-writing of your model with private objects as presented in the tsp.py example you still run into errors, please provide a minimal reproducible example describing the issue.
1 -
-
Hi,
Thanks for everything.
I was successful in my project and I believe I understood enough for future implementations ^^0 -
投稿コメントは受け付けていません。
コメント
7件のコメント