Skip to main content

Lazy constraints can not be added to the model.

Answered

Comments

3 comments

  • Marika Karbstein
    • Gurobi Staff Gurobi Staff

    Can you please provide a minimum reproducible example? See Tutorial: Preparing a Minimal Reproducible Example

    What do you mean by constraint cannot be added? Do you see any error messages?

    0
  • Chenshi Jia
    • Gurobi-versary
    • First Question
    • First Comment

    Hi,

    To describe my issue, I add a set of continuous variables to the TSP problem in the Gurobi example for callback. The detailed model can be seen:

    The detailed code can be seen:

    import math
    import random
    from itertools import combinations
    import gurobipy as gp
    from gurobipy import GRB

    random.seed(1)


    # Callback - use lazy constraints to eliminate sub-tours
    def subtourelim(model, where):
        if where == GRB.Callback.MIPSOL:
            vals = model.cbGetSolution(model._vars)
            print(vals)
            eta = model.cbGetSolution(model._eta)
            print('------')
            print(eta)
            # find the shortest cycle in the selected edge list
            tour = subtour(vals)
            if len(tour) < n:
                print(" --- exists subtour --- ")
                # add subtour elimination constr. for every pair of cities in tour
                model.cbLazy(gp.quicksum(model._vars[i, j]
                                         for i, j in combinations(tour, 2))
                             <= len(tour)-1)
            for i in range(n):
                if eta[i] > 1:
                    model.cbLazy(model._eta[i] <= 1)
                    print(model._eta[i] <= 1)

    def subtour(vals):
        # make a list of edges selected in the solution
        edges = gp.tuplelist((i, j) for i, j in vals.keys()
                             if vals[i, j] > 0.5)
        unvisited = list(range(n))
        cycle = range(n+1)  # initial length has 1 more city
        while unvisited:  # true if list is non-empty
            thiscycle = []
            neighbors = unvisited
            while neighbors:
                current = neighbors[0]
                thiscycle.append(current)
                unvisited.remove(current)
                neighbors = [j for i, j in edges.select(current, '*')
                             if j in unvisited]
            if len(cycle) > len(thiscycle):
                cycle = thiscycle
        return cycle

    n = int(6)
    nodes = [i for i in range(n)]

    # Create n random points

    random.seed(1)
    points = [(random.randint(0, 100), random.randint(0, 100)) for i in range(n)]

    # Dictionary of Euclidean distance between each pair of points

    dist = {(i, j):
            math.sqrt(sum((points[i][k]-points[j][k])**2 for k in range(2)))
            for i in range(n) for j in range(i)}

    m = gp.Model()

    # Create variables

    vars = m.addVars(dist.keys(), vtype=GRB.BINARY, name='e')
    for i, j in vars.keys():
        vars[j, i] = vars[i, j]  # edge in opposite direction
        
    var3 = m.addVars(nodes, vtype=GRB.CONTINUOUS, name='eta')
    obj = var3.sum()
    m.setObjective(obj, gp.GRB.MAXIMIZE)

    m.addConstrs(vars.sum(i, '*') == 2 for i in range(n))

    m._vars = vars
    m._eta = var3
    m.Params.LazyConstraints = 1
    m.optimize(subtourelim)

    vals = m.getAttr('X', vars)
    tour = subtour(vals)
    assert len(tour) == n

    print('')
    print('Optimal tour: %s' % str(tour))
    print('Optimal cost: %g' % m.ObjVal)
    print('')

    Obviously, the optimal value of each eta should be 1. But I get 'model is unbounded'. The lazy constraints about eta can be printed. So I guess the lazy constraints are not added. But I don't know why. Please suggest.

    0
  • Marika Karbstein
    • Gurobi Staff Gurobi Staff

    You defined an unbounded model that is detected to be unbounded in the root relaxation.
    During presolve a solution is checked in your callback for feasibility. That's why you see the output of lazy constraints. So, the found solution is refused but the unboundedness is detected anyway.
    You need to make the model bounded. If you set the upper bound of the eta-variable to a large value, you will see that your lazy constraints work and force eta to be less than or equal to 1.

    But this is a very strange way of defining the model. If you know bounds for the variables, define them right away and not by using lazy constraints.

    1

Please sign in to leave a comment.