Gurobi Python: Summation Constraint with Multiplication not being satisfied.
I am adding MILP equation which provides a feasible solution. However, somehow one of the constraint pertaining to the distance is not being satisfied as in the following equation:
Which is coded using the following expression:
for i in range(n-1):
opt_model.addConstr((grb.quicksum(x_vars[i,j]*distance(points, i, j) for j in range(1,n))) <= 25)
I am obtaining a solution in which individual edges x(i,j) are less then the distance or upper bound instead of their "summation" to be less then the distance or upper bound. The following is full reproducible code:
import random
import gurobipy as grb
import math
n = 10
Distance = 25
def distance(points, i, j):
dx = points[i][0] - points[j][0]
dy = points[i][1] - points[j][1]
return math.sqrt(dx*dx + dy*dy)
random.seed(1)
points = []
for i in range(n):
points.append((random.randint(0,100),random.randint(0,100)))
opt_model = grb.Model(name="MILP Model")
# <= Variables
x_vars = {}
for i in range(n):
for j in range(n):
x_vars[i,j] = opt_model.addVar(vtype=grb.GRB.BINARY,
name='e'+str(i)+'_'+str(j))
u={}
for i in range(1,n):
u[i]=opt_model.addVar(vtype=grb.GRB.INTEGER,
name='e'+str(i))
# <= Constraint (Mandatory Edges and excluding vertexes) Eq(1)
opt_model.addConstr((grb.quicksum(x_vars[1,j] for j in range(1,n))) == 1)
opt_model.addConstr((grb.quicksum(x_vars[i,(n-1)] for i in range(n-1))) == 1)
opt_model.addConstr((grb.quicksum(x_vars[i,i] for i in range(n-1))) == 0)
# <= Constraint (Distance) Eq(3)
for i in range(n-1):
opt_model.addConstr((grb.quicksum(x_vars[i,j]*distance(points, i, j) for j in range(1,n))) <= Distance)
# <= Constraint (Equality & Single edge in and out) Eq(2)
for k in range(1, n-1):
opt_model.addConstr(grb.quicksum(x_vars[i,k] for i in range(n-1))
== grb.quicksum(x_vars[k,j] for j in range(1, n)) <=1)
for k in range(1, n-1):
opt_model.addConstr(grb.quicksum(x_vars[i,k] for i in range(n-1))
<=1)
for k in range(1, n - 1):
opt_model.addConstr(grb.quicksum(x_vars[k, j] for j in range(1, n))
<= 1)
# <= Constraint (Subtour elimination) Eq(4) Eq(5)
for i in range(1,n):
opt_model.addConstr(2 <= u[i] <= n)
for i in range(1,n):
for j in range(1,n):
opt_model.addConstr((u[i] - u[j] +1 <= (n-1)*(1-x_vars[j,i])))
# <= objective (maximize) Eq(1)
objective = grb.quicksum(x_vars[i,j]
for i in range(1, n-1)
for j in range(1, n))
opt_model.ModelSense = grb.GRB.MAXIMIZE
opt_model.setObjective(objective)
opt_model.update()
opt_model.optimize()
solution = opt_model.getAttr('x', x_vars )
select = grb.tuplelist((i,j) for i,j in x_vars.keys() if x_vars[i,j].X > 0.5)
for i in range(len(select)):
print points[select[i][0]],points[select[i][1]]
print distance(points,select[i][0],select[i][1])
-
正式なコメント
-
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 why not try our AI Gurobot?. -
-
-
Hi Abdul,
Your code is currently adding a constraint for every \( i = 1, ..., N-1 \). In particular, the code corresponds to the following \( N - 1 \) constraints:
$$ \sum_{j = 2}^N t_{ij} x_{ij} \leq T_{\text{max}} \quad i = 1, ..., N-1 $$
Instead, you should incorporate the for loop into the summation:
opt_model.addConstr((grb.quicksum(x_vars[i,j]*distance(points, i, j) for j in range(1,n) for i in range(n-1))) <= Distance)
I hope this helps!
Eli
1 -
-
Dear Eli,
Yes it solved the problem!. Also kudos for illustrating what the existing code was doing. So the code was merely adding a constraint on i, i.e. what values it can take, but was not permutating the values of i with j and summing that up. Right?
Best,
Abdul
0 -
-
-
Hi Abdul,
The code was adding a constraint for every \( i \) rather than a single constraint that sums over every value of \( i \). You can tell this immediately by looking at the structure of the code:
for i in range(n-1):
opt_model.addConstr(...)Here, we are looping over the addConstr() method N-1 times. This means N-1 constraints are added to the model, which doesn't match what we want to do. If we want to add a single constraint, we should only call the addConstr() method once.
Thanks!
Eli
1 -
-
Dear Eli,
Quite nicely explained!
Thanks a lot!
Abdul0 -
-
Dear Eli,
I have one last question pertaining to the constraints. Can we add multiple constraints in a single expression or it has to be separated. Consider the following equation:
Can this be written down as:
for k in range(1, n-1):
opt_model.addConstr(grb.quicksum(x_vars[i,k] for i in range(n-1))
== grb.quicksum(x_vars[k,j] for j in range(1, n)))
for k in range(1, n-1):
opt_model.addConstr(grb.quicksum(x_vars[i,k] for i in range(n-1))
<=1)
for k in range(1, n-1):
opt_model.addConstr(grb.quicksum(x_vars[k, j] for j in range(1, n))
<= 1)Instead of a single equation as :
for k in range(1, n-1):
opt_model.addConstr(grb.quicksum(x_vars[i,k] for i in range(n-1))
== grb.quicksum(x_vars[k,j] for j in range(1, n)) <= 1)Because the results differ in each case.
0 -
-
-
Hi Abdul,
In the Gurobi 8.1 documentation for Model.addConstr(), there is a warning that adding multiple constraints via the addConstr() method is not supported. In Gurobi 9.0 (scheduled for release in a few weeks), your second code snippet will result in an error.
Hence, you should use the first approach to add these two sets of constraints. I have two brief comments:
- The third set of constraints isn't necessary, because this constraint family is implied by the first two. For example, if you add constraints that \(x = y\) and \(x \leq 1\), then the constraint \(y \leq 1\) will automatically be satisfied.
- The Model.addConstrs() method is perfectly suited for situations where you are adding constraints in a for loop. With this method, you can enforce these constraints in two lines:
opt_model.addConstrs((grb.quicksum(x_vars[i,k] for i in range(n-1)) == grb.quicksum(x_vars[k,j] for j in range(1, n))) for k in range(1, n-1))
opt_model.addConstrs((grb.quicksum(x_vars[i,k] for i in range(n-1)) <= 1) for k in range(1, n-1))I hope this helps. Thanks!
Eli
1 -
-
Dear Eli,
Wow Awsome! Great explanation with good insights!
I shall remove the redundancy and make my code compact.
Cheers,
Abdul
0 -
投稿コメントは受け付けていません。
コメント
8件のコメント