3.6.2 Cazzaro and Pisinger 2022 G-140 and G-210¶
This is used in the paper Flexible cable routing framework for wind farm collection system optimization.
[1]:
import pickle
from importlib.resources import files
[2]:
from optiwindnet.interarraylib import G_from_S
from optiwindnet.svg import svgplot
from optiwindnet.mesh import make_planar_embedding
from optiwindnet.baselines.hgs import hgs_cvrp
from optiwindnet.importer import L_from_yaml
from optiwindnet.pathfinding import PathFinder
from optiwindnet.MILP import solver_factory, ModelOptions
from optiwindnet.interarraylib import as_normalized
Reference solutions¶
Cazzaro, D., & Pisinger, D. (2022). Balanced cable routing for offshore wind farms with obstacles. Networks, 80(4), 386–406. https://doi.org/10.1002/net.22100
[3]:
G140_ref = pickle.load(open('data/cazzaro_2022G_140_paper_routeset.pkl', 'rb'))
[4]:
svgplot(G140_ref)
[4]:
[5]:
G210_ref = pickle.load(open('data/cazzaro_2022G_210_paper_routeset.pkl', 'rb'))
[6]:
svgplot(G210_ref)
[6]:
Start here¶
Instantiate solver¶
[7]:
solver = solver_factory('gurobi')
G-140, κ = 6¶
[8]:
L140 = L_from_yaml(files('optiwindnet.data') / 'Cazzaro-2022G-140.yaml')
[9]:
svgplot(L140)
[9]:
[10]:
P, A = make_planar_embedding(L140)
A_norm = as_normalized(A)
[11]:
Sʹ = hgs_cvrp(A_norm, capacity=6, time_limit=0.5, balanced=True)
Sʹ.graph['solution_time']
[11]:
(0.2, 0.03, 0.06)
[12]:
Gʹ = G_from_S(Sʹ, A)
svgplot(Gʹ)
[12]:
[13]:
[[Sʹ[r][n]['load'] for n in Sʹ[r]] for r in range(-3, 0)]
[13]:
[[6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6], [5, 5, 5, 6, 6, 6, 5, 6]]
[14]:
Hʹ = PathFinder(Gʹ, planar=P, A=A, branched=False).create_detours()
svgplot(Hʹ)
[14]:
[15]:
Hʹ.size(weight='length')/G140_ref.size(weight='length') - 1
[15]:
0.010633899773379252
[16]:
solver.set_problem(
P, A,
capacity=Sʹ.graph['capacity'],
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
balanced=True,
),
warmstart=Sʹ,
)
Set parameter WLSAccessID
Set parameter WLSSecret
Set parameter LicenseID to value 937681
Set parameter MIPFocus to value 1
Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
[17]:
solver.solve(
mip_gap=0.005,
time_limit=10,
verbose=True,
options=dict(
mipfocus=1,
),
)
Set parameter TimeLimit to value 10
Set parameter MIPGap to value 0.005
Gurobi Optimizer version 13.0.2 build v13.0.2rc1 (linux64 - "Debian GNU/Linux forky/sid")
CPU model: 11th Gen Intel(R) Core(TM) i7-11850H @ 2.50GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Non-default parameters:
TimeLimit 10
MIPGap 0.005
MIPFocus 1
Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
Optimize a model with 5391 rows, 3328 columns and 20386 nonzeros (Min)
Model fingerprint: 0xcc62cf88
Model has 1664 linear objective coefficients
Variable types: 0 continuous, 3328 integer (1664 binary)
Coefficient statistics:
Matrix range [1e+00, 6e+00]
Objective range [4e+02, 2e+04]
Bounds range [1e+00, 6e+00]
RHS range [1e+00, 1e+02]
Loaded user MIP start with objective 243298
Presolve removed 950 rows and 0 columns
Presolve time: 0.03s
Presolved: 4441 rows, 3328 columns, 18066 nonzeros
Variable types: 0 continuous, 3328 integer (1664 binary)
Root relaxation: objective 2.199192e+05, 4346 iterations, 0.08 seconds (0.12 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 219919.222 0 306 243297.915 219919.222 9.61% - 0s
H 0 0 242528.56393 219919.222 9.32% - 0s
0 0 224024.485 0 482 242528.564 224024.485 7.63% - 0s
0 0 224183.264 0 472 242528.564 224183.264 7.56% - 0s
0 0 224204.108 0 488 242528.564 224204.108 7.56% - 0s
0 0 224204.122 0 490 242528.564 224204.122 7.56% - 0s
0 0 225644.855 0 586 242528.564 225644.855 6.96% - 0s
0 0 225805.715 0 558 242528.564 225805.715 6.90% - 0s
0 0 225833.919 0 577 242528.564 225833.919 6.88% - 0s
0 0 225835.726 0 581 242528.564 225835.726 6.88% - 0s
0 0 225835.821 0 590 242528.564 225835.821 6.88% - 0s
H 0 0 241364.06683 225835.821 6.43% - 1s
0 0 226666.040 0 625 241364.067 226666.040 6.09% - 1s
H 0 0 240932.33913 226916.616 5.82% - 1s
H 0 0 240027.30176 226916.616 5.46% - 1s
H 0 0 239271.37537 226916.616 5.16% - 1s
0 0 226916.616 0 639 239271.375 226916.616 5.16% - 1s
0 0 226991.941 0 668 239271.375 226991.941 5.13% - 1s
0 0 227013.300 0 668 239271.375 227013.300 5.12% - 1s
0 0 227018.357 0 669 239271.375 227018.357 5.12% - 1s
0 0 227019.239 0 675 239271.375 227019.239 5.12% - 1s
0 0 227020.110 0 680 239271.375 227020.110 5.12% - 1s
0 0 227020.230 0 678 239271.375 227020.230 5.12% - 1s
H 0 0 238259.69021 227020.230 4.72% - 1s
0 0 227408.728 0 651 238259.690 227408.728 4.55% - 2s
0 0 227501.352 0 662 238259.690 227501.352 4.52% - 2s
0 0 227536.136 0 655 238259.690 227536.136 4.50% - 2s
0 0 227547.108 0 673 238259.690 227547.108 4.50% - 2s
0 0 227552.603 0 664 238259.690 227552.603 4.49% - 2s
0 0 227554.000 0 665 238259.690 227554.000 4.49% - 2s
0 0 227554.635 0 662 238259.690 227554.635 4.49% - 2s
H 0 0 237905.84359 227554.635 4.35% - 2s
0 0 227774.128 0 666 237905.844 227774.128 4.26% - 2s
0 0 227774.128 0 665 237905.844 227774.128 4.26% - 2s
H 0 0 237867.55145 227774.128 4.24% - 3s
H 0 0 237669.59619 227774.128 4.16% - 3s
0 2 227774.128 0 665 237669.596 227774.128 4.16% - 7s
H 16 24 237580.58750 227911.957 4.07% 340 7s
H 119 121 237545.38948 227911.957 4.06% 205 9s
H 128 137 237380.64628 227911.957 3.99% 201 9s
H 150 156 237085.09534 227911.957 3.87% 200 9s
H 179 190 236730.14738 227911.957 3.72% 191 9s
H 182 190 236706.80469 227911.957 3.72% 192 9s
189 194 230472.952 20 486 236706.805 227911.957 3.72% 191 10s
Cutting planes:
Gomory: 33
Cover: 1
Implied bound: 3
MIR: 284
StrongCG: 8
Flow cover: 80
Flow path: 9
GUB cover: 3
Zero half: 3
Network: 41
RLT: 6
Relax-and-lift: 4
Explored 193 nodes (47068 simplex iterations) in 10.01 seconds (12.01 work units)
Thread count was 16 (of 16 available processors)
Solution count 10: 236707 236730 237085 ... 238260
Time limit reached
Best objective 2.367068046913e+05, best bound 2.279119572090e+05, gap 3.7155%
[17]:
SolutionInfo(runtime=10.013159036636353, bound=227911.95720904972, objective=236706.80469130888, relgap=0.03715502599821152, termination='maxTimeLimit')
[18]:
S140, G140 = solver.get_solution()
svgplot(G140)
[18]:
[19]:
[[G140[r][n]['load'] for n in G140[r]] for r in range(-3, 0)]
[19]:
[[6, 6, 6, 6, 6, 6, 6, 5, 6, 6], [6, 6, 6, 5, 5, 6], [5, 6, 6, 6, 6, 6, 6, 6]]
[20]:
1 - G140.size(weight='length')/G140_ref.size(weight='length')
[20]:
0.020539760123712503
[21]:
pickle.dump(G140, open('cazzaro_2022G_140_κ_6_radial_balanced_our.pkl', 'wb'))
G-210, κ = 7¶
[22]:
L210 = L_from_yaml(files('optiwindnet.data') / 'Cazzaro-2022G-210.yaml')
[23]:
P, A = make_planar_embedding(L210)
A_norm = as_normalized(A)
[24]:
svgplot(L210)
[24]:
[25]:
Sʹ = hgs_cvrp(A_norm, capacity=7, time_limit=1, balanced=True)
Sʹ.graph['solution_time']
[25]:
(0.27, 0.22, 0.51)
[26]:
Gʹ = G_from_S(Sʹ, A)
Hʹ = PathFinder(Gʹ, planar=P, A=A, branched=False).create_detours()
svgplot(Hʹ)
[26]:
[27]:
1- Hʹ.size(weight='length')/G210_ref.size(weight='length')
[27]:
0.015090421048965408
Solve the balanced MILP model¶
[28]:
solver.set_problem(
P, A,
capacity=Sʹ.graph['capacity'],
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
balanced=True,
),
warmstart=Sʹ,
)
Set parameter WLSAccessID
Set parameter WLSSecret
Set parameter LicenseID to value 937681
Set parameter MIPFocus to value 1
Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
[29]:
solver.solve(
mip_gap=0.005,
time_limit=95,
verbose=True,
options=dict(
mipfocus=1,
),
)
Set parameter TimeLimit to value 95
Set parameter MIPGap to value 0.005
Gurobi Optimizer version 13.0.2 build v13.0.2rc1 (linux64 - "Debian GNU/Linux forky/sid")
CPU model: 11th Gen Intel(R) Core(TM) i7-11850H @ 2.50GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Non-default parameters:
TimeLimit 95
MIPGap 0.005
MIPFocus 1
Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
Optimize a model with 7784 rows, 5212 columns and 30812 nonzeros (Min)
Model fingerprint: 0xf696931d
Model has 2606 linear objective coefficients
Variable types: 0 continuous, 5212 integer (2606 binary)
Coefficient statistics:
Matrix range [1e+00, 7e+00]
Objective range [3e+02, 2e+04]
Bounds range [1e+00, 7e+00]
RHS range [1e+00, 2e+02]
Loaded user MIP start with objective 296625
Presolve removed 860 rows and 0 columns
Presolve time: 0.04s
Presolved: 6924 rows, 5212 columns, 28462 nonzeros
Variable types: 0 continuous, 5212 integer (2606 binary)
Root relaxation: objective 2.696831e+05, 6324 iterations, 0.13 seconds (0.20 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 269683.061 0 526 296624.904 269683.061 9.08% - 0s
0 0 274277.951 0 769 296624.904 274277.951 7.53% - 0s
0 0 274571.751 0 817 296624.904 274571.751 7.43% - 0s
0 0 274597.129 0 800 296624.904 274597.129 7.43% - 0s
0 0 274597.152 0 805 296624.904 274597.152 7.43% - 0s
0 0 275993.201 0 854 296624.904 275993.201 6.96% - 1s
0 0 276193.358 0 900 296624.904 276193.358 6.89% - 1s
0 0 276262.880 0 888 296624.904 276262.880 6.86% - 1s
0 0 276266.627 0 895 296624.904 276266.627 6.86% - 1s
0 0 276267.210 0 908 296624.904 276267.210 6.86% - 1s
0 0 277003.755 0 968 296624.904 277003.755 6.61% - 2s
0 0 277330.323 0 953 296624.904 277330.323 6.50% - 2s
0 0 277404.433 0 1011 296624.904 277404.433 6.48% - 2s
0 0 277422.988 0 1019 296624.904 277422.988 6.47% - 2s
0 0 277429.192 0 1022 296624.904 277429.192 6.47% - 2s
0 0 277431.335 0 1002 296624.904 277431.335 6.47% - 2s
0 0 277431.828 0 1000 296624.904 277431.828 6.47% - 2s
0 0 277874.350 0 1001 296624.904 277874.350 6.32% - 3s
0 0 278036.269 0 998 296624.904 278036.269 6.27% - 3s
0 0 278117.804 0 1011 296624.904 278117.804 6.24% - 3s
0 0 278138.647 0 1032 296624.904 278138.647 6.23% - 4s
0 0 278152.493 0 1043 296624.904 278152.493 6.23% - 4s
0 0 278155.979 0 1031 296624.904 278155.979 6.23% - 4s
0 0 278157.066 0 1029 296624.904 278157.066 6.23% - 4s
0 0 278157.878 0 1050 296624.904 278157.878 6.23% - 4s
0 0 278466.311 0 1008 296624.904 278466.311 6.12% - 4s
0 0 278466.311 0 1008 296624.904 278466.311 6.12% - 4s
0 2 278466.311 0 1008 296624.904 278466.311 6.12% - 11s
H 37 40 296210.60741 278754.502 5.89% 341 12s
H 70 76 296017.81457 278754.502 5.83% 298 14s
83 92 279224.122 12 994 296017.815 278754.502 5.83% 290 15s
163 172 280843.111 19 882 296017.815 278754.502 5.83% 269 20s
243 252 281935.657 25 798 296017.815 278754.502 5.83% 254 25s
308 322 282030.266 32 825 296017.815 278754.502 5.83% 237 30s
634 655 292347.101 68 717 296017.815 278754.502 5.83% 199 35s
919 1003 279039.439 7 943 296017.815 278771.569 5.83% 172 40s
1605 1525 289058.265 75 1008 296017.815 278785.479 5.82% 170 45s
1617 1533 279302.463 5 1040 296017.815 279036.566 5.74% 169 50s
1638 1547 286434.339 57 1142 296017.815 279677.413 5.52% 167 56s
1639 1548 279677.503 12 1142 296017.815 279677.503 5.52% 167 69s
1642 1555 279841.912 17 1069 296017.815 279708.412 5.51% 180 70s
1842 1693 280975.517 29 1061 296017.815 279868.918 5.46% 194 75s
1921 1745 281659.936 33 951 296017.815 279868.918 5.46% 197 80s
1972 1779 284866.331 36 952 296017.815 279868.918 5.46% 197 85s
2020 1811 287039.616 39 941 296017.815 279868.918 5.46% 197 90s
2074 1835 279963.068 20 1023 296017.815 279890.882 5.45% 198 95s
Cutting planes:
Gomory: 23
Cover: 4
Implied bound: 1
Clique: 1
MIR: 413
StrongCG: 10
Flow cover: 272
Flow path: 5
Zero half: 7
Network: 21
RLT: 10
Relax-and-lift: 18
BQP: 4
Explored 2082 nodes (426959 simplex iterations) in 95.01 seconds (131.31 work units)
Thread count was 16 (of 16 available processors)
Solution count 3: 296018 296211 296625
Time limit reached
Best objective 2.960178145692e+05, best bound 2.798908820533e+05, gap 5.4480%
[29]:
SolutionInfo(runtime=95.01480197906494, bound=279890.88205334573, objective=296017.8145692225, relgap=0.05447960130151408, termination='maxTimeLimit')
[30]:
S210, G210 = solver.get_solution()
svgplot(G210)
[30]:
[31]:
1 - G210.size(weight='length')/G210_ref.size(weight='length')
[31]:
0.017104134057788767
[32]:
pickle.dump(G210, open('cazzaro_2022G_210_κ_7_radial_balanced_our.pkl', 'wb'))