3.6.1 Yi et at 2019¶

[1]:

import pickle

[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_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 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]:

../_images/notebooks_44-Paper_3.6.1_Yi_2019_comparison_12_0.svg

Solve κ = 6 (branched)¶

[9]:

Sʹ = hgs_cvrp(A_norm, capacity=6, time_limit=0.5, vehicles=20)
Sʹ.graph['solution_time']

[9]:

(0.32, 0.29)

[10]:

Gʹ = G_from_S(Sʹ, A)
Hʹ = PathFinder(Gʹ, planar=P, A=A).create_detours()
svgplot(Hʹ)

[10]:

../_images/notebooks_44-Paper_3.6.1_Yi_2019_comparison_15_0.svg

[11]:

1 - Hʹ.size(weight='length')/λ_branched

[11]:

0.11463530574482794

[12]:

solver.set_problem(
    P, A_norm,
    capacity=Sʹ.graph['capacity'],
    model_options=ModelOptions(
        topology="branched",
        feeder_route="segmented",
        feeder_limit="minimum",
    ),
    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

[13]:

solver.solve(
    mip_gap=0.005,
    time_limit=20,
    verbose=True,
    options=dict(mipfocus=1),
)

Set parameter TimeLimit to value 20
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  20
MIPGap  0.005
MIPFocus  1

Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
Optimize a model with 3851 rows, 2592 columns and 14304 nonzeros (Min)
Model fingerprint: 0x8d79edd8
Model has 1296 linear objective coefficients
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 413 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, 2584 iterations, 0.04 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  176   10.78438    9.96630  7.59%     -    0s
H    0     0                      10.7811045    9.96630  7.56%     -    0s
H    0     0                      10.7795357    9.96630  7.54%     -    0s
     0     0   10.19127    0  232   10.77954   10.19127  5.46%     -    0s
     0     0   10.20597    0  214   10.77954   10.20597  5.32%     -    0s
H    0     0                      10.7785494   10.25069  4.90%     -    0s
     0     0   10.25069    0  294   10.77855   10.25069  4.90%     -    0s
     0     0   10.25723    0  281   10.77855   10.25723  4.84%     -    0s
H    0     0                      10.7753028   10.25723  4.81%     -    0s
H    0     0                      10.7273324   10.25723  4.38%     -    0s
     0     0   10.28803    0  308   10.72733   10.28803  4.10%     -    0s
H    0     0                      10.7263461   10.28803  4.09%     -    0s
H    0     0                      10.7261654   10.28803  4.08%     -    0s
     0     0   10.29462    0  366   10.72617   10.29462  4.02%     -    0s
     0     0   10.30371    0  367   10.72617   10.30371  3.94%     -    0s
H    0     0                      10.7027515   10.30861  3.68%     -    0s
     0     0   10.30861    0  406   10.70275   10.30861  3.68%     -    0s
     0     0   10.31338    0  415   10.70275   10.31338  3.64%     -    0s
     0     0   10.31338    0  415   10.70275   10.31338  3.64%     -    0s
     0     0   10.31338    0  413   10.70275   10.31338  3.64%     -    0s
H    0     0                      10.6956337   10.31338  3.57%     -    1s
H    0     0                      10.6941302   10.31338  3.56%     -    1s
H    0     0                      10.6941182   10.31338  3.56%     -    1s
H    0     0                      10.6741297   10.31338  3.38%     -    1s
     0     2   10.31338    0  413   10.67413   10.31338  3.38%     -    3s
H  149   152                      10.5936841   10.32702  2.52%   127    4s
H  152   155                      10.5863545   10.32702  2.45%   125    4s
H  220   193                      10.5858274   10.32776  2.44%   106    4s
   601   475   10.48054   23  236   10.58583   10.32921  2.42%  82.0    5s
  1788  1277   10.47471   21  503   10.58583   10.37664  1.98%  65.8   10s
  1994  1429   10.41075   20  501   10.58583   10.38260  1.92%  80.6   15s
  4368  2227   10.48230   29  242   10.58583   10.39241  1.83%  89.8   20s

Cutting planes:
  Gomory: 22
  Lift-and-project: 12
  Cover: 10
  Implied bound: 1
  MIR: 239
  StrongCG: 15
  Flow cover: 201
  Flow path: 13
  GUB cover: 7
  Zero half: 5
  Mod-K: 5
  Network: 17
  Relax-and-lift: 9

Explored 4389 nodes (398510 simplex iterations) in 20.01 seconds (22.94 work units)
Thread count was 16 (of 16 available processors)

Solution count 10: 10.5858 10.5864 10.5937 ... 10.7263

Time limit reached
Best objective 1.058582742936e+01, best bound 1.039241405855e+01, gap 1.8271%

[13]:

SolutionInfo(runtime=20.016806840896606, bound=10.392414058546652, objective=10.585827429361387, relgap=0.01827097334671013, termination='maxTimeLimit')

[14]:

S, G = solver.get_solution(A)
svgplot(G)

[14]:

../_images/notebooks_44-Paper_3.6.1_Yi_2019_comparison_19_0.svg

[15]:

1 - G.size(weight='length')/λ_branched

[15]:

0.13398784961608867

[16]:

pickle.dump(G, open('yi_2019_κ_6_branched_our.pkl', 'wb'))

Solve κ = 6 (radial)¶

[17]:

Sʹ = hgs_cvrp(A_norm, capacity=6, time_limit=0.5, vehicles=20)
Sʹ.graph['solution_time']

[17]:

(0.33, 0.16)

[18]:

Gʹ = G_from_S(Sʹ, A)
Hʹ = PathFinder(Gʹ, planar=P, A=A).create_detours()
svgplot(Hʹ)

[18]:

../_images/notebooks_44-Paper_3.6.1_Yi_2019_comparison_24_0.svg

[19]:

1 - Hʹ.size(weight='length')/λ_radial

[19]:

0.15663966893499937

[20]:

solver.set_problem(
    P, A_norm,
    capacity=Sʹ.graph['capacity'],
    model_options=ModelOptions(
        topology="radial",
        feeder_route="segmented",
        feeder_limit="minimum",
    ),
    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

[21]:

solver.solve(
    mip_gap=0.005,
    time_limit=20,
    verbose=True,
    options=dict(mipfocus=1),
)

Set parameter TimeLimit to value 20
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  20
MIPGap  0.005
MIPFocus  1

Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
Optimize a model with 3970 rows, 2592 columns and 15362 nonzeros (Min)
Model fingerprint: 0x28e963e0
Model has 1296 linear objective coefficients
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 413 rows and 0 columns
Presolve time: 0.02s
Presolved: 3557 rows, 2592 columns, 14298 nonzeros
Variable types: 0 continuous, 2592 integer (1296 binary)

Root relaxation: objective 9.993809e+00, 2894 iterations, 0.06 seconds (0.08 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0    9.99381    0  271   10.78438    9.99381  7.33%     -    0s
     0     0   10.23002    0  275   10.78438   10.23002  5.14%     -    0s
     0     0   10.24150    0  235   10.78438   10.24150  5.03%     -    0s
     0     0   10.29047    0  421   10.78438   10.29047  4.58%     -    0s
     0     0   10.30026    0  387   10.78438   10.30026  4.49%     -    0s
     0     0   10.33105    0  349   10.78438   10.33105  4.20%     -    0s
     0     0   10.34404    0  410   10.78438   10.34404  4.08%     -    0s
     0     0   10.35894    0  441   10.78438   10.35894  3.95%     -    1s
     0     0   10.36245    0  454   10.78438   10.36245  3.91%     -    1s
     0     0   10.36781    0  511   10.78438   10.36781  3.86%     -    1s
     0     0   10.36781    0  508   10.78438   10.36781  3.86%     -    1s
     0     2   10.36791    0  508   10.78438   10.36791  3.86%     -    2s
   215   231   10.56143   22  354   10.78438   10.37662  3.78%   142    5s
H 1032   786                      10.7050175   10.38491  2.99%   101    9s
  1452  1082   10.42692   24  431   10.70502   10.38785  2.96%  93.7   10s
H 1699  1149                      10.6880722   10.38925  2.80%  90.3   12s
  1716  1160   10.62642   22  513   10.68807   10.41105  2.59%  89.4   17s
  2045  1368   10.56994   29  389   10.68807   10.41733  2.53%   112   20s

Cutting planes:
  Gomory: 17
  Lift-and-project: 3
  Cover: 5
  Implied bound: 5
  MIR: 155
  StrongCG: 4
  Flow cover: 127
  Flow path: 1
  GUB cover: 4
  Zero half: 1
  Mod-K: 2
  Network: 20
  RLT: 8
  Relax-and-lift: 17

Explored 2064 nodes (238443 simplex iterations) in 20.01 seconds (23.04 work units)
Thread count was 16 (of 16 available processors)

Solution count 3: 10.6881 10.705 10.7844

Time limit reached
Best objective 1.068807224015e+01, best bound 1.041733142791e+01, gap 2.5331%

[21]:

SolutionInfo(runtime=20.01891589164734, bound=10.417331427908284, objective=10.688072240152739, relgap=0.025331117357846877, termination='maxTimeLimit')

[22]:

S, G = solver.get_solution(A)
svgplot(G)

[22]:

../_images/notebooks_44-Paper_3.6.1_Yi_2019_comparison_28_0.svg

[23]:

1 - G.size(weight='length')/λ_radial

[23]:

0.16841447876500804

[24]:

pickle.dump(G, open('yi_2019_κ_6_radial_our.pkl', 'wb'))