Skip to main content

Lazy Constraints / TSP

Answered
Roberval Gonçalves Moreira Filho
  • Gurobi-versary
  • First Comment
  • First Question

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 ^^

0

Comments

7 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • 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.
  • Jaromił Najman
    • Gurobi Staff

    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
  • Roberval Gonçalves Moreira Filho
    Edited
    • Gurobi-versary
    • First Comment
    • First Question

    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
  • Jaromił Najman
    • Gurobi Staff

    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
  • Roberval Gonçalves Moreira Filho
    • Gurobi-versary
    • First Comment
    • First Question

    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:

    https://support.gurobi.com/hc/en-us/articles/360013197972-How-do-I-implement-lazy-constraints-in-Gurobi-

    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
  • Jaromił Najman
    • Gurobi Staff

    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
  • Roberval Gonçalves Moreira Filho
    • Gurobi-versary
    • First Comment
    • First Question

    Hi,
    Thanks for everything.
    I was successful in my project and I believe I understood enough for future implementations ^^

    0

Post is closed for comments.

Didn't find what you were looking for?

New post