3.6.1 Yi et at 2019¶
[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.4, 0.19)
[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,
options=dict(mipfocus=1),
)
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: 0xcba7b093
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, 2583 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.7838118 9.96630 7.58% - 0s
H 0 0 10.7811045 9.96630 7.56% - 0s
0 0 10.19355 0 253 10.78110 10.19355 5.45% - 0s
H 0 0 10.7810924 10.19355 5.45% - 0s
0 0 10.21049 0 278 10.78109 10.21049 5.29% - 0s
H 0 0 10.7801181 10.21049 5.28% - 0s
0 0 10.23879 0 321 10.78012 10.23879 5.02% - 0s
H 0 0 10.7795237 10.25316 4.88% - 0s
0 0 10.25316 0 360 10.77952 10.25316 4.88% - 0s
H 0 0 10.7785494 10.25316 4.87% - 0s
0 0 10.29090 0 373 10.77855 10.29090 4.52% - 0s
H 0 0 10.7499115 10.29090 4.27% - 0s
0 0 10.29297 0 370 10.74991 10.29297 4.25% - 0s
0 0 10.30518 0 428 10.74991 10.30518 4.14% - 1s
0 0 10.31095 0 393 10.74991 10.31095 4.08% - 1s
0 0 10.31744 0 404 10.74991 10.31744 4.02% - 1s
H 0 0 10.7498995 10.31744 4.02% - 1s
H 0 0 10.7298198 10.31744 3.84% - 1s
H 0 0 10.7098313 10.31744 3.66% - 1s
H 0 0 10.7046838 10.31744 3.62% - 2s
H 0 0 10.7032476 10.31744 3.60% - 2s
H 0 0 10.6862326 10.31744 3.45% - 2s
0 2 10.31744 0 404 10.68623 10.31744 3.45% - 3s
H 2 4 10.6789043 10.31760 3.38% 39.5 3s
H 38 47 10.5988086 10.32040 2.63% 106 3s
H 95 110 10.5973051 10.32040 2.61% 83.4 3s
H 101 110 10.5882100 10.32040 2.53% 82.3 3s
502 418 10.37280 9 378 10.58821 10.32465 2.49% 59.3 5s
1780 1381 10.50956 24 470 10.58821 10.34722 2.28% 46.5 10s
1815 1422 10.36715 16 548 10.58821 10.36681 2.09% 53.4 15s
3418 2092 10.50582 59 316 10.58821 10.37819 1.98% 73.0 20s
6337 3467 10.43055 17 434 10.58821 10.37819 1.98% 72.9 25s
8389 4848 10.40273 26 469 10.58821 10.38048 1.96% 74.2 30s
11369 7210 10.49668 51 271 10.58821 10.38631 1.91% 74.2 35s
14890 9478 10.51558 27 277 10.58821 10.39555 1.82% 74.3 40s
19040 12379 10.46359 50 275 10.58821 10.39802 1.80% 73.8 45s
Cutting planes:
Gomory: 33
Lift-and-project: 11
Cover: 12
MIR: 309
StrongCG: 22
Flow cover: 262
Flow path: 22
GUB cover: 3
Inf proof: 2
Zero half: 5
Mod-K: 2
Network: 23
RLT: 1
Relax-and-lift: 19
Explored 19359 nodes (1426603 simplex iterations) in 45.07 seconds (40.81 work units)
Thread count was 16 (of 16 available processors)
Solution count 10: 10.5882 10.5973 10.5988 ... 10.7499
Time limit reached
Best objective 1.058820995844e+01, best bound 1.039802485227e+01, gap 1.7962%
WARNING: Loading a SolverResults object with an 'aborted' status, but
containing a solution
[16]:
SolutionInfo(runtime=45.0789999961853, bound=10.398024852271213, objective=10.588209958443283, relgap=0.017961969673675804, 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.43, 0.19)
[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,
options=dict(mipfocus=1),
)
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: 0x66fae53e
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, 2717 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.23156 0 312 10.78438 10.23156 5.13% - 0s
0 0 10.23895 0 213 10.78438 10.23895 5.06% - 0s
0 0 10.28063 0 428 10.78438 10.28063 4.67% - 0s
0 0 10.28480 0 463 10.78438 10.28480 4.63% - 0s
0 0 10.31555 0 373 10.78438 10.31555 4.35% - 1s
0 0 10.32560 0 378 10.78438 10.32560 4.25% - 1s
0 0 10.33688 0 506 10.78438 10.33688 4.15% - 1s
0 0 10.34033 0 527 10.78438 10.34033 4.12% - 1s
0 0 10.34858 0 531 10.78438 10.34858 4.04% - 1s
0 2 10.34858 0 531 10.78438 10.34858 4.04% - 3s
130 156 10.46052 16 460 10.78438 10.35578 3.97% 158 5s
H 491 420 10.7481569 10.36319 3.58% 108 7s
H 769 585 10.7465553 10.36589 3.54% 98.6 8s
H 785 611 10.7346593 10.36589 3.44% 98.2 8s
H 961 619 10.6529319 10.36653 2.69% 94.7 9s
1097 751 10.44789 24 353 10.65293 10.36653 2.69% 92.9 10s
1933 1249 10.56392 24 267 10.65293 10.37083 2.65% 84.9 15s
H 1949 1196 10.6165820 10.40574 1.99% 84.2 16s
H 1949 1136 10.6160549 10.40574 1.98% 84.2 16s
1956 1141 10.61605 18 588 10.61605 10.41279 1.91% 83.9 22s
2361 1298 cutoff 32 10.61605 10.43016 1.75% 97.7 25s
3822 1762 10.60183 57 159 10.61605 10.44196 1.64% 101 30s
6364 2803 10.53591 27 344 10.61605 10.45398 1.53% 96.2 35s
8725 4141 10.54727 32 398 10.61605 10.46102 1.46% 97.0 40s
11636 5553 10.50132 31 369 10.61605 10.46639 1.41% 96.5 45s
Cutting planes:
Gomory: 22
Cover: 4
Implied bound: 2
Clique: 2
MIR: 284
StrongCG: 12
Flow cover: 230
Flow path: 19
GUB cover: 7
Zero half: 8
Network: 20
RLT: 8
Relax-and-lift: 34
Explored 11661 nodes (1130643 simplex iterations) in 45.09 seconds (43.12 work units)
Thread count was 16 (of 16 available processors)
Solution count 7: 10.6161 10.6166 10.6529 ... 10.7844
Time limit reached
Best objective 1.061605486611e+01, best bound 1.046638765619e+01, gap 1.4098%
WARNING: Loading a SolverResults object with an 'aborted' status, but
containing a solution
[28]:
SolutionInfo(runtime=45.09099984169006, bound=10.466387656186585, objective=10.61605486611012, relgap=0.014098194838962352, termination='maxTimeLimit')
[29]:
S, G = solver.get_solution(A)
[30]:
svgplot(G)
[30]:
[31]:
1 - G.size(weight='length')/λ_radial
[31]:
0.17072176123560445
[32]:
with open('yi_2019_κ_6_radial_our.dill', 'wb') as outfile:
dill.dump(G, outfile)