Lazy constraints can not be added to the model.
AnsweredHi,
I’m currently facing a problem.
There are two sets of variables A and B. The objective function is to maximize the summation of A. The constraints are only about B in the model. I want to add lazy constraints about A by the callback function. When using it, I find that the lazy constraints are printed correctly but can not added to the model. And it is strange that when I give an upper bound to B, the lazy constraints can be added correctly. (The numbers in the "ro" list range from 0 to 1.)
def Twocuts(model, where):
if where == GRB.Callback.MIPSOL:
x = model.cbGetSolution(model._x)
eta = model.cbGetSolution(model._eta)
ro = calFillRate(x)
for i in range(n):
if ro[i] > eta[i]:
model.cbLazy(model._eta[i] >= ro[i])
model.update()
m = gp.Model()
var = m.addVars(dist.keys(), vtype=GRB.BINARY, name='e')
for i, j in var.keys():
var[j, i] = var[i, j]
var3 = m.addVars(nodes, vtype=GRB.CONTINUOUS, ub=1, name='eta')
obj = var3.sum()
m.setObjective(obj, gp.GRB.MINIMIZE)
m.addConstrs(var.sum(i, '*') == 2 for i in range(n))
m._x = var
m._eta = var3
m.params.lazyConstraints = 1
m.optimize(Twocuts)
Please suggest.
-
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 -
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 -
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.
Comments
3 comments