[1]:
import dill
[2]:
from importlib.resources import files
[3]:
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_multiroot
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 solution¶
Yi, X., Scutariu, M., & Smith, K. (2019). Optimisation of offshore wind farm inter-array collection system. IET Renewable Power Generation, 13(11), 1990–1999. https://doi.org/10.1049/iet-rpg.2018.5805
The network was not parsed from the paper, using the published total cable lengths:
radial: 162.3 km
branched: 154.6 km
[4]:
λ_radial = 162300
λ_branched = 154600
Start here¶
[5]:
solver = solver_factory('gurobi')
[6]:
base_dir = files('optiwindnet.data')
inputfile = base_dir / 'Yi-2019.yaml'
L = L_from_yaml(inputfile)
[7]:
P, A = make_planar_embedding(L)
A_norm = as_normalized(A)
[8]:
svgplot(A)
[8]:
Solve κ = 6 (branched)¶
[9]:
Sʹ = hgs_multiroot(A_norm, capacity=6, time_limit=0.5)
[10]:
Sʹ.graph['solution_time']
[10]:
(0.24, 0.2)
[11]:
Gʹ = G_from_S(Sʹ, A)
[12]:
Hʹ = PathFinder(Gʹ, planar=P, A=A).create_detours()
[13]:
svgplot(Hʹ)
[13]:
[14]:
1 - Hʹ.size(weight='length')/λ_branched
[14]:
0.11463530574482794
[15]:
solver.set_problem(
P, A_norm,
capacity=Sʹ.graph['capacity'],
model_options=ModelOptions(
topology="branched",
feeder_route="segmented",
feeder_limit="minimum",
),
warmstart=Sʹ,
)
[16]:
solver.solve(
mip_gap=0.005,
time_limit=45,
verbose=True,
)
Set parameter OutputFlag to value 1
Gurobi Optimizer version 12.0.2 build v12.0.2rc0 (win64 - Windows 11.0 (26100.2))
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 45
MIPGap 0.005
MIPFocus 1
Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
Optimize a model with 3852 rows, 2592 columns and 14542 nonzeros
Model fingerprint: 0x73289d33
Variable types: 0 continuous, 2592 integer (1296 binary)
Coefficient statistics:
Matrix range [1e+00, 6e+00]
Objective range [5e-02, 1e+00]
Bounds range [1e+00, 6e+00]
RHS range [1e+00, 1e+02]
Loaded user MIP start with objective 10.7844
Presolve removed 414 rows and 0 columns
Presolve time: 0.02s
Presolved: 3438 rows, 2592 columns, 13240 nonzeros
Variable types: 0 continuous, 2592 integer (1296 binary)
Root relaxation: objective 9.966300e+00, 2570 iterations, 0.05 seconds (0.06 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 9.96630 0 177 10.78438 9.96630 7.59% - 0s
H 0 0 10.7811045 9.96630 7.56% - 0s
H 0 0 10.7810924 9.96630 7.56% - 0s
0 0 10.19621 0 203 10.78109 10.19621 5.43% - 0s
0 0 10.20900 0 227 10.78109 10.20900 5.31% - 0s
H 0 0 10.7801061 10.20900 5.30% - 0s
0 0 10.24309 0 340 10.78011 10.24309 4.98% - 0s
0 0 10.25246 0 340 10.78011 10.25246 4.89% - 0s
H 0 0 10.7768595 10.25246 4.87% - 0s
H 0 0 10.7752908 10.25246 4.85% - 0s
0 0 10.27779 0 333 10.77529 10.27779 4.62% - 0s
H 0 0 10.7553023 10.27779 4.44% - 0s
0 0 10.28714 0 390 10.75530 10.28714 4.35% - 0s
0 0 10.31266 0 402 10.75530 10.31266 4.12% - 1s
0 0 10.32084 0 399 10.75530 10.32084 4.04% - 1s
0 0 10.32617 0 394 10.75530 10.32617 3.99% - 1s
H 0 0 10.7065847 10.32617 3.55% - 1s
0 2 10.32618 0 394 10.70658 10.32618 3.55% - 3s
H 56 65 10.7000010 10.33991 3.37% 71.9 3s
H 125 129 10.6754713 10.33991 3.14% 76.9 3s
H 150 166 10.6439278 10.33991 2.86% 76.8 4s
316 322 10.41571 29 322 10.64393 10.33991 2.86% 69.2 5s
H 1209 934 10.6075080 10.34766 2.45% 67.3 7s
H 1693 1304 10.6069388 10.34766 2.44% 62.7 8s
1704 1312 10.38427 22 325 10.60694 10.35130 2.41% 62.3 10s
1721 1323 10.44380 29 473 10.60694 10.37906 2.15% 61.7 15s
H 1872 1373 10.5883958 10.38233 1.95% 76.3 16s
H 1911 1329 10.5881854 10.38233 1.94% 77.1 17s
2658 1572 10.40815 29 294 10.58819 10.38840 1.89% 78.7 20s
4951 2397 10.46417 30 214 10.58819 10.39554 1.82% 77.0 25s
8161 4555 10.51005 44 300 10.58819 10.39933 1.78% 73.7 30s
10194 6240 10.49454 45 192 10.58819 10.40518 1.73% 73.3 35s
13383 8359 10.50696 36 263 10.58819 10.40785 1.70% 74.0 40s
16578 10641 10.49905 32 316 10.58819 10.41065 1.68% 73.3 45s
Cutting planes:
Gomory: 30
Lift-and-project: 8
Cover: 9
MIR: 273
StrongCG: 15
Flow cover: 258
Flow path: 24
GUB cover: 3
Inf proof: 4
Zero half: 8
Mod-K: 8
Network: 24
RLT: 2
Relax-and-lift: 24
Explored 17019 nodes (1248869 simplex iterations) in 45.10 seconds (38.49 work units)
Thread count was 16 (of 16 available processors)
Solution count 10: 10.5882 10.5884 10.6069 ... 10.7753
Time limit reached
Best objective 1.058818539829e+01, best bound 1.041067879649e+01, gap 1.6765%
WARNING: Loading a SolverResults object with an 'aborted' status, but
containing a solution
[16]:
SolutionInfo(runtime=45.104000091552734, bound=10.410678796494933, objective=10.588185398286745, relgap=0.016764591392641637, termination='maxTimeLimit')
[17]:
S, G = solver.get_solution(A)
[18]:
svgplot(G)
[18]:
[19]:
1 - G.size(weight='length')/λ_branched
[19]:
0.13379531445617387
[20]:
with open('yi_2019_κ_6_branched_our.dill', 'wb') as outfile:
dill.dump(G, outfile)
Solve κ = 6 (radial)¶
[21]:
Sʹ = hgs_multiroot(A_norm, capacity=6, time_limit=0.5)
[22]:
Sʹ.graph['solution_time']
[22]:
(0.24, 0.22)
[23]:
Gʹ = G_from_S(Sʹ, A)
[24]:
Hʹ = PathFinder(Gʹ, planar=P, A=A).create_detours()
[25]:
svgplot(Hʹ)
[25]:
[26]:
1 - Hʹ.size(weight='length')/λ_radial
[26]:
0.15663966893499937
[27]:
solver.set_problem(
P, A_norm,
capacity=Sʹ.graph['capacity'],
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
),
warmstart=Sʹ,
)
[28]:
solver.solve(
mip_gap=0.005,
time_limit=45,
verbose=True,
)
Set parameter OutputFlag to value 1
Gurobi Optimizer version 12.0.2 build v12.0.2rc0 (win64 - Windows 11.0 (26100.2))
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 45
MIPGap 0.005
MIPFocus 1
Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
Optimize a model with 3971 rows, 2592 columns and 15600 nonzeros
Model fingerprint: 0xdfb2120a
Variable types: 0 continuous, 2592 integer (1296 binary)
Coefficient statistics:
Matrix range [1e+00, 6e+00]
Objective range [5e-02, 1e+00]
Bounds range [1e+00, 6e+00]
RHS range [1e+00, 1e+02]
Loaded user MIP start with objective 10.7844
Presolve removed 414 rows and 0 columns
Presolve time: 0.03s
Presolved: 3557 rows, 2592 columns, 14298 nonzeros
Variable types: 0 continuous, 2592 integer (1296 binary)
Root relaxation: objective 9.993809e+00, 2711 iterations, 0.06 seconds (0.07 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 9.99381 0 272 10.78438 9.99381 7.33% - 0s
0 0 10.23528 0 264 10.78438 10.23528 5.09% - 0s
0 0 10.24537 0 222 10.78438 10.24537 5.00% - 0s
0 0 10.29685 0 396 10.78438 10.29685 4.52% - 0s
0 0 10.29831 0 437 10.78438 10.29831 4.51% - 0s
0 0 10.32524 0 426 10.78438 10.32524 4.26% - 1s
0 0 10.33421 0 433 10.78438 10.33421 4.17% - 1s
0 0 10.34880 0 412 10.78438 10.34880 4.04% - 1s
0 0 10.35163 0 426 10.78438 10.35163 4.01% - 1s
0 0 10.35809 0 503 10.78438 10.35809 3.95% - 1s
0 2 10.35809 0 503 10.78438 10.35809 3.95% - 3s
124 133 10.44603 13 375 10.78438 10.36403 3.90% 151 5s
H 143 149 10.7091014 10.36403 3.22% 144 5s
H 181 189 10.6735219 10.36403 2.90% 132 5s
H 238 231 10.6518236 10.36403 2.70% 116 5s
H 244 231 10.6284535 10.36403 2.49% 115 5s
H 405 328 10.6165574 10.37161 2.31% 108 6s
H 519 428 10.6160303 10.37195 2.30% 99.3 6s
1860 1274 10.55361 35 503 10.61603 10.38491 2.18% 83.1 10s
1887 1292 10.45514 10 518 10.61603 10.41366 1.91% 81.9 17s
2132 1434 10.60680 28 282 10.61603 10.42099 1.84% 96.1 20s
3987 1890 infeasible 30 10.61603 10.43638 1.69% 99.2 25s
5945 2368 10.48695 31 462 10.61603 10.45163 1.55% 95.9 30s
8370 3832 10.57026 32 437 10.61603 10.45367 1.53% 94.9 35s
11416 5222 10.48369 32 352 10.61603 10.46313 1.44% 95.2 40s
14397 6657 10.51434 32 516 10.61603 10.46749 1.40% 94.5 45s
Cutting planes:
Gomory: 30
Cover: 6
Implied bound: 1
Clique: 1
MIR: 279
StrongCG: 14
Flow cover: 235
Flow path: 20
GUB cover: 8
Inf proof: 1
Zero half: 11
Network: 28
RLT: 14
Relax-and-lift: 47
Explored 14620 nodes (1385819 simplex iterations) in 45.09 seconds (42.01 work units)
Thread count was 16 (of 16 available processors)
Solution count 7: 10.616 10.6166 10.6285 ... 10.7844
Time limit reached
Best objective 1.061603030595e+01, best bound 1.046749133406e+01, gap 1.3992%
WARNING: Loading a SolverResults object with an 'aborted' status, but
containing a solution
[28]:
SolutionInfo(runtime=45.09699988365173, bound=10.46749133406285, objective=10.616030305953581, relgap=0.013991950626537797, termination='maxTimeLimit')
[29]:
S, G = solver.get_solution(A)
[30]:
svgplot(G)
[30]:
[31]:
1 - G.size(weight='length')/λ_radial
[31]:
0.17117956054543038
[32]:
with open('yi_2019_κ_6_radial_our.dill', 'wb') as outfile:
dill.dump(G, outfile)