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.2, 0.18)

[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ʹ,
)

[13]:

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

Gurobi Optimizer version 13.0.1 build v13.0.1rc0 (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: 0x65002c48
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.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  176   10.78438    9.96630  7.59%     -    0s
H    0     0                      10.7838118    9.96630  7.58%     -    0s
H    0     0                      10.7826433    9.96630  7.57%     -    0s
H    0     0                      10.7795357    9.96630  7.54%     -    0s
     0     0   10.19127    0  232   10.77954   10.19127  5.46%     -    0s
H    0     0                      10.7785494   10.20597  5.31%     -    0s
     0     0   10.20597    0  214   10.77855   10.20597  5.31%     -    0s
     0     0   10.25100    0  291   10.77855   10.25100  4.89%     -    0s
     0     0   10.25411    0  281   10.77855   10.25411  4.87%     -    0s
H    0     0                      10.7508027   10.28130  4.37%     -    0s
     0     0   10.28130    0  331   10.75080   10.28130  4.37%     -    0s
H    0     0                      10.7308181   10.28130  4.19%     -    0s
H    0     0                      10.7308061   10.28130  4.19%     -    0s
     0     0   10.28888    0  384   10.73081   10.28888  4.12%     -    0s
     0     0   10.31224    0  412   10.73081   10.31224  3.90%     -    0s
     0     0   10.31601    0  405   10.73081   10.31601  3.87%     -    0s
     0     0   10.32512    0  429   10.73081   10.32512  3.78%     -    1s
     0     0   10.32512    0  429   10.73081   10.32512  3.78%     -    1s
H    0     0                      10.7298197   10.32513  3.77%     -    1s
H    0     0                      10.6335110   10.32513  2.90%     -    1s
     0     2   10.32513    0  429   10.63351   10.32513  2.90%     -    2s
H   10    16                      10.6269273   10.32694  2.82%   130    2s
H  107   132                      10.6069388   10.33078  2.60%   113    3s
   574   479     cutoff   56        10.60694   10.34051  2.51%  73.4    5s
  1757  1307   10.52810   44  499   10.60694   10.36738  2.26%  70.2   12s
  2451  1592     cutoff   29        10.60694   10.38507  2.09%  83.8   15s
H 4540  2397                      10.5979851   10.39067  1.96%  77.8   18s
H 4719  2345                      10.5883958   10.39067  1.87%  78.0   19s
  5292  2675   10.48365   37  329   10.58840   10.39275  1.85%  77.4   20s

Cutting planes:
  Gomory: 31
  Lift-and-project: 8
  Cover: 7
  Implied bound: 2
  MIR: 235
  StrongCG: 13
  Flow cover: 223
  Flow path: 11
  GUB cover: 6
  Inf proof: 1
  Zero half: 6
  Mod-K: 2
  Network: 14
  RLT: 3
  Relax-and-lift: 6

Explored 5397 nodes (419778 simplex iterations) in 20.01 seconds (21.18 work units)
Thread count was 16 (of 16 available processors)

Solution count 10: 10.5884 10.598 10.6069 ... 10.7785

Time limit reached
Best objective 1.058839583731e+01, best bound 1.039274956261e+01, gap 1.8477%

[13]:

SolutionInfo(runtime=20.017431020736694, bound=10.392749562605308, objective=10.588395837311046, relgap=0.018477423559886685, 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.133778131485372

[16]:

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

Solve κ = 6 (radial)¶

[17]:

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

[17]:

(0.18, 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ʹ,
)

[21]:

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

Gurobi Optimizer version 13.0.1 build v13.0.1rc0 (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: 0x0b20da36
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.07 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  386   10.78438   10.30026  4.49%     -    0s
     0     0   10.33638    0  407   10.78438   10.33638  4.15%     -    0s
     0     0   10.34419    0  466   10.78438   10.34419  4.08%     -    0s
     0     0   10.35800    0  454   10.78438   10.35800  3.95%     -    0s
     0     0   10.36209    0  417   10.78438   10.36209  3.92%     -    0s
     0     0   10.36516    0  494   10.78438   10.36516  3.89%     -    1s
     0     0   10.36516    0  494   10.78438   10.36516  3.89%     -    1s
     0     0   10.36516    0  494   10.78438   10.36516  3.89%     -    1s
     0     2   10.36516    0  494   10.78438   10.36516  3.89%     -    2s
   209   213   10.54179   20  270   10.78438   10.36787  3.86%   120    5s
H  232   229                      10.6156510   10.36878  2.33%   121    5s
H  446   413                      10.6027805   10.37185  2.18%   115    5s
  1800  1297   10.47211   22  441   10.60278   10.38496  2.05%  90.5   10s
  1854  1376   10.43710   16  558   10.60278   10.42993  1.63%   101   15s
  2988  1650   10.53838   25  298   10.60278   10.44098  1.53%   112   20s

Cutting planes:
  Gomory: 16
  Lift-and-project: 4
  Cover: 8
  Implied bound: 1
  MIR: 194
  StrongCG: 10
  Flow cover: 178
  Flow path: 12
  GUB cover: 6
  Zero half: 5
  Network: 30
  RLT: 10
  Relax-and-lift: 29

Explored 3016 nodes (341589 simplex iterations) in 20.02 seconds (23.18 work units)
Thread count was 16 (of 16 available processors)

Solution count 3: 10.6028 10.6157 10.7844

Time limit reached
Best objective 1.060278049610e+01, best bound 1.044098394953e+01, gap 1.5260%

[21]:

SolutionInfo(runtime=20.02225613594055, bound=10.440983949525778, objective=10.602780496104984, relgap=0.015259822330438988, 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.15954875643014943

[24]:

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