Constraint not working as intended
回答済みHello,
Thank you for reading my question. I am trying to select a series of arcs based on maximized benefit and contiguity. However, I am having trouble with constraint 5, introducing the variable aij. Aij is supposed to be 1 if xij in a neighborhood set is 1. However, my code generates a 1 for all Aijs and I cannot figure out why. Any insights to offer? Thanks in advance.



#cost along arcs
c=[9,6,8,2,3,8,5,7,8,5,9,2,6,4,7,3,8,6,6,5,7,8,4,4,4,4,5,3,3,9,6,7]
#benefit along arcs
b=[5,2,4,6,7,4,9,3,4,9,5,6,2,8,3,7,4,2,2,9,3,4,8,8,8,8,9,7,7,5,2,3]
B = 25 #Budget
e = .1 #contiguity efficiency parameter
# Neighborhood set of arcs
Ni = [
[1, 2, 3, 6, 5],
[0, 2, 3, 4, 7, 8],
[0, 1, 4, 9, 10],
[0, 1, 4, 5, 6, 7, 8],
[1, 2, 3, 7, 8, 9, 10],
[0, 3, 6, 12, 16, 17],
[0, 3, 5, 7, 11, 12, 13],
[1, 3, 4, 6, 8, 11, 12, 13],
[1, 3, 4, 7, 9, 11, 14, 15],
[2, 4, 8, 10, 11, 14, 15],
[2, 4, 9, 15, 20, 21],
[6, 7, 8, 9, 10, 12, 13, 14, 15],
[5, 6, 7, 11, 13, 16, 17],
[6, 7, 11, 12, 14, 18, 19],
[8, 9, 11, 13, 15, 18, 19],
[8, 9, 10, 11, 14, 20, 21],
[5, 12, 17, 23, 27, 29],
[5, 12, 16, 18, 22, 23, 24],
[13, 14, 17, 19, 22, 23, 24],
[13, 14, 18, 20, 22, 25, 26],
[10, 15, 19, 21, 22, 25, 26],
[10, 15, 20, 26, 28, 31],
[17, 18, 19, 20, 23, 24, 25, 26],
[16, 17, 18, 22, 23, 24, 27, 29],
[17, 18, 22, 23, 25, 27, 28, 30],
[19, 20, 22, 24, 26, 27, 28, 30],
[19, 20, 21, 22, 25, 28, 31],
[16, 23, 24, 25, 28, 29, 30],
[21, 24, 25, 26, 27, 30, 31],
[16, 23, 27, 30, 31],
[24, 25, 27, 28, 29, 31],
[21, 26, 28, 29, 30],
]
from gurobipy import Model, GRB, quicksum
m = Model("Pedestrian")
x = {}
for ArcNum in range(0, 32):
x[ArcNum] = m.addVar(vtype=GRB.BINARY)
a = {}
for ArcNum in range(0, 32):
a[ArcNum] = m.addVar(vtype=GRB.BINARY)
# Budget Constraint
m.addConstr(
quicksum(c[ArcNum] * x[ArcNum] for ArcNum in range(0, 32)),
GRB.LESS_EQUAL,
B,
"BudgetConstraint",
)
# contiguity indicator aij; aij = 1 if xij has a contiguous neighbor being repaired and 0 otherwise
for ArcNum in range(0, 32):
m.addConstr(
a[ArcNum], GRB.LESS_EQUAL, quicksum(x[Neighbors] for Neighbors in Ni[ArcNum])
)
m.setObjective(
quicksum(b[ArcNum] * x[ArcNum] for ArcNum in range(0, 32))
+ (quicksum(a[ArcNum] * b[ArcNum] * e for ArcNum in range(0, 32)))
)
m.update()
m.modelSense = GRB.MAXIMIZE
m.optimize()
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (win64)
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 33 rows, 64 columns and 282 nonzeros
Model fingerprint: 0x6984ba11
Variable types: 0 continuous, 64 integer (64 binary)
Coefficient statistics:
Matrix range [1e+00, 9e+00]
Objective range [2e-01, 9e+00]
Bounds range [1e+00, 1e+00]
RHS range [3e+01, 3e+01]
Found heuristic solution: objective 22.8000000
Presolve time: 0.00s
Presolved: 33 rows, 64 columns, 282 nonzeros
Variable types: 0 continuous, 64 integer (64 binary)
Root relaxation: objective 7.530000e+01, 16 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 75.30000 0 1 22.80000 75.30000 230% - 0s
H 0 0 74.3000000 75.30000 1.35% - 0s
Cutting planes:
Gomory: 1
Explored 1 nodes (16 simplex iterations) in 0.02 seconds
Thread count was 12 (of 12 available processors)
Solution count 2: 74.3 22.8
Optimal solution found (tolerance 1.00e-04)
Best objective 7.430000000000e+01, best bound 7.430000000000e+01, gap 0.0000%
x
{0: <gurobi.Var C0 (value 0.0)>,
1: <gurobi.Var C1 (value 0.0)>,
2: <gurobi.Var C2 (value 0.0)>,
3: <gurobi.Var C3 (value 1.0)>,
4: <gurobi.Var C4 (value 1.0)>,
5: <gurobi.Var C5 (value 0.0)>,
6: <gurobi.Var C6 (value 0.0)>,
7: <gurobi.Var C7 (value 0.0)>,
8: <gurobi.Var C8 (value 0.0)>,
9: <gurobi.Var C9 (value 0.0)>,
10: <gurobi.Var C10 (value 0.0)>,
11: <gurobi.Var C11 (value 1.0)>,
12: <gurobi.Var C12 (value 0.0)>,
13: <gurobi.Var C13 (value 1.0)>,
14: <gurobi.Var C14 (value 0.0)>,
15: <gurobi.Var C15 (value 0.0)>,
16: <gurobi.Var C16 (value 0.0)>,
17: <gurobi.Var C17 (value 0.0)>,
18: <gurobi.Var C18 (value 0.0)>,
19: <gurobi.Var C19 (value 0.0)>,
20: <gurobi.Var C20 (value 0.0)>,
21: <gurobi.Var C21 (value 0.0)>,
22: <gurobi.Var C22 (value 1.0)>,
23: <gurobi.Var C23 (value 0.0)>,
24: <gurobi.Var C24 (value 1.0)>,
25: <gurobi.Var C25 (value 0.0)>,
26: <gurobi.Var C26 (value 0.0)>,
27: <gurobi.Var C27 (value 1.0)>,
28: <gurobi.Var C28 (value 1.0)>,
29: <gurobi.Var C29 (value 0.0)>,
30: <gurobi.Var C30 (value 0.0)>,
31: <gurobi.Var C31 (value 0.0)>}
a
{0: <gurobi.Var C32 (value 1.0)>,
1: <gurobi.Var C33 (value 1.0)>,
2: <gurobi.Var C34 (value 1.0)>,
3: <gurobi.Var C35 (value 1.0)>,
4: <gurobi.Var C36 (value 1.0)>,
5: <gurobi.Var C37 (value 1.0)>,
6: <gurobi.Var C38 (value 1.0)>,
7: <gurobi.Var C39 (value 1.0)>,
8: <gurobi.Var C40 (value 1.0)>,
9: <gurobi.Var C41 (value 1.0)>,
10: <gurobi.Var C42 (value 1.0)>,
11: <gurobi.Var C43 (value 1.0)>,
12: <gurobi.Var C44 (value 1.0)>,
13: <gurobi.Var C45 (value 1.0)>,
14: <gurobi.Var C46 (value 1.0)>,
15: <gurobi.Var C47 (value 1.0)>,
16: <gurobi.Var C48 (value 1.0)>,
17: <gurobi.Var C49 (value 1.0)>,
18: <gurobi.Var C50 (value 1.0)>,
19: <gurobi.Var C51 (value 1.0)>,
20: <gurobi.Var C52 (value 1.0)>,
21: <gurobi.Var C53 (value 1.0)>,
22: <gurobi.Var C54 (value 1.0)>,
23: <gurobi.Var C55 (value 1.0)>,
24: <gurobi.Var C56 (value 1.0)>,
25: <gurobi.Var C57 (value 1.0)>,
26: <gurobi.Var C58 (value 1.0)>,
27: <gurobi.Var C59 (value 1.0)>,
28: <gurobi.Var C60 (value 1.0)>,
29: <gurobi.Var C61 (value 1.0)>,
30: <gurobi.Var C62 (value 1.0)>,
31: <gurobi.Var C63 (value 1.0)>}
0
-
正式なコメント
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 Penelope,
I am not sure what \(x\) and \(a\) represent in your model but apparently, every single sum \(\sum_{N_{ij}} x_{ij}\) is \(\geq 1\). You are also trying to maximize a sum that contains \(a\), so it shouldn't be surprising that all are set to 1.
On a different note: You should define your variables like this:
x = m.addVars(range(32), vtype=GRB.BINARY)
a = m.addVars(range(32), vtype=GRB.BINARY)I hope this helps.
Cheers,
Matthias0
投稿コメントは受け付けていません。
コメント
2件のコメント