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 dill
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_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 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 = dill.load(open('data/cazzaro_2022G_140_paper_routeset.dill', 'rb'))
[4]:
svgplot(G140_ref)
[4]:
[5]:
G210_ref = dill.load(open('data/cazzaro_2022G_210_paper_routeset.dill', 'rb'))
[6]:
svgplot(G210_ref)
[6]:
Start here¶
Instantiate solver¶
[7]:
solver = solver_factory('gurobi')
G-140, κ = 6¶
[56]:
L140 = L_from_yaml(files('optiwindnet.data') / 'Cazzaro-2022G-140.yaml')
[57]:
svgplot(L140)
[57]:
[58]:
P, A = make_planar_embedding(L140)
A_norm = as_normalized(A)
[59]:
Sʹ = hgs_multiroot(A_norm, capacity=6, time_limit=0.5, balanced=True)
[60]:
Sʹ.graph['solution_time']
[60]:
(0.41, 0.04, 0.22)
[61]:
Gʹ = G_from_S(Sʹ, A)
[62]:
svgplot(Gʹ)
[62]:
[63]:
[[Sʹ[r][n]['load'] for n in Sʹ[r]] for r in range(-3, 0)]
[63]:
[[6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6], [5, 5, 5, 6, 6, 6, 5, 6]]
[64]:
Hʹ = PathFinder(Gʹ, planar=P, A=A, branched=False).create_detours()
[65]:
svgplot(Hʹ)
[65]:
[66]:
Hʹ.size(weight='length')/G140_ref.size(weight='length') - 1
[66]:
0.01422305639439081
[67]:
solver.set_problem(
P, A,
capacity=Sʹ.graph['capacity'],
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
balanced=True,
),
warmstart=Sʹ,
)
[68]:
solver.solve(
mip_gap=0.005,
time_limit=10,
verbose=True,
options=dict(
mipfocus=1,
RINS=100,
CutPasses=4,
VarBranch=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 10
MIPGap 0.005
MIPFocus 1
RINS 100
VarBranch 1
CutPasses 4
Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
Optimize a model with 5480 rows, 3388 columns and 21198 nonzeros
Model fingerprint: 0x96a337c4
Variable types: 0 continuous, 3388 integer (1694 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 967 rows and 0 columns
Presolve time: 0.02s
Presolved: 4513 rows, 3388 columns, 18426 nonzeros
Variable types: 0 continuous, 3388 integer (1694 binary)
Root relaxation: objective 2.199122e+05, 4317 iterations, 0.09 seconds (0.12 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 219912.178 0 310 243297.969 219912.178 9.61% - 0s
H 0 0 242528.61779 219912.178 9.33% - 0s
0 0 223896.916 0 516 242528.618 223896.916 7.68% - 0s
0 0 224016.460 0 514 242528.618 224016.460 7.63% - 0s
0 0 224021.381 0 525 242528.618 224021.381 7.63% - 0s
0 0 224023.472 0 524 242528.618 224023.472 7.63% - 0s
0 0 225407.123 0 592 242528.618 225407.123 7.06% - 0s
0 0 225602.899 0 643 242528.618 225602.899 6.98% - 0s
H 0 0 242183.75078 225690.237 6.81% - 1s
0 0 225690.237 0 637 242183.751 225690.237 6.81% - 1s
0 0 225709.871 0 637 242183.751 225709.871 6.80% - 1s
0 0 225712.887 0 647 242183.751 225712.887 6.80% - 1s
0 0 225714.300 0 644 242183.751 225714.300 6.80% - 1s
0 0 225714.354 0 646 242183.751 225714.354 6.80% - 1s
H 0 0 241615.53053 226471.157 6.27% - 1s
0 0 226471.157 0 655 241615.531 226471.157 6.27% - 1s
H 0 0 241364.12069 226471.157 6.17% - 1s
0 0 226635.955 0 659 241364.121 226635.955 6.10% - 1s
0 0 226709.998 0 635 241364.121 226709.998 6.07% - 1s
0 0 226715.282 0 639 241364.121 226715.282 6.07% - 1s
0 0 226715.824 0 645 241364.121 226715.824 6.07% - 1s
0 0 227040.537 0 656 241364.121 227040.537 5.93% - 2s
H 0 0 241189.12632 227040.999 5.87% - 3s
H 0 0 238512.20561 227040.999 4.81% - 3s
H 0 0 238186.72680 227040.999 4.68% - 3s
H 0 0 237756.27923 227040.999 4.51% - 3s
0 2 227040.999 0 656 237756.279 227040.999 4.51% - 3s
H 52 54 237590.81979 227256.387 4.35% 195 4s
H 80 89 237571.79303 227256.387 4.34% 166 4s
112 121 227653.474 17 667 237571.793 227256.387 4.34% 163 5s
H 120 129 237015.37629 227256.387 4.12% 161 5s
H 147 156 236660.42833 227256.387 3.97% 165 5s
H 241 244 236637.08564 227256.387 3.96% 168 6s
604 561 228174.031 13 575 236637.086 227336.507 3.93% 142 10s
Cutting planes:
Gomory: 34
Cover: 4
Implied bound: 3
MIR: 260
StrongCG: 10
Flow cover: 81
Flow path: 11
GUB cover: 5
Zero half: 3
Mod-K: 1
Network: 40
RLT: 8
Relax-and-lift: 8
Explored 629 nodes (98453 simplex iterations) in 10.04 seconds (10.12 work units)
Thread count was 16 (of 16 available processors)
Solution count 10: 236637 236660 237015 ... 241364
Time limit reached
Best objective 2.366370856382e+05, best bound 2.273365073120e+05, gap 3.9303%
WARNING: Loading a SolverResults object with an 'aborted' status, but
containing a solution
[68]:
SolutionInfo(runtime=10.043999910354614, bound=227336.5073120126, objective=236637.0856382203, relgap=0.03930313078832781, termination='maxTimeLimit')
[69]:
S140, G140 = solver.get_solution()
[70]:
[[G140[r][n]['load'] for n in G140[r]] for r in range(-3, 0)]
[70]:
[[6, 6, 6, 6, 6, 6, 6, 5, 6, 6], [6, 6, 6, 5, 5, 6], [5, 6, 6, 6, 6, 6, 6, 6]]
[71]:
1 - G140.size(weight='length')/G140_ref.size(weight='length')
[71]:
0.020828468287038326
[72]:
svgplot(G140)
[72]:
[73]:
with open('cazzaro_2022G_140_κ_6_radial_balanced_our.dill', 'wb') as outfile:
dill.dump(G140, outfile)
G-210, κ = 7¶
[38]:
L210 = L_from_yaml(files('optiwindnet.data') / 'Cazzaro-2022G-210.yaml')
[39]:
P, A = make_planar_embedding(L210)
A_norm = as_normalized(A)
[40]:
svgplot(L210)
[40]:
[41]:
Sʹ = hgs_multiroot(A_norm, capacity=7, time_limit=1)
[42]:
Sʹ.graph['solution_time']
[42]:
(0.35, 0.26, 0.33)
[43]:
Gʹ = G_from_S(Sʹ, A)
[44]:
Hʹ = PathFinder(Gʹ, planar=P, A=A, branched=False).create_detours()
[45]:
svgplot(Hʹ)
[45]:
[46]:
1- Hʹ.size(weight='length')/G210_ref.size(weight='length')
[46]:
0.01517110172331404
Solve the balanced MILP model¶
90 s Gurobi¶
[50]:
solver.set_problem(
P, A,
capacity=Sʹ.graph['capacity'],
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
balanced=True,
),
warmstart=Sʹ,
)
[51]:
solver.solve(
mip_gap=0.005,
time_limit=90,
verbose=True,
options=dict(
mipfocus=1,
RINS=100,
CutPasses=4,
VarBranch=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 90
MIPGap 0.005
MIPFocus 1
RINS 100
VarBranch 1
CutPasses 4
Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
Optimize a model with 7924 rows, 5304 columns and 32058 nonzeros
Model fingerprint: 0x68736103
Variable types: 0 continuous, 5304 integer (2652 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 296615
Presolve removed 891 rows and 0 columns
Presolve time: 0.09s
Presolved: 7033 rows, 5304 columns, 29018 nonzeros
Variable types: 0 continuous, 5304 integer (2652 binary)
Root relaxation: objective 2.696831e+05, 6521 iterations, 0.21 seconds (0.23 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 269683.061 0 522 296615.310 269683.061 9.08% - 0s
0 0 274175.257 0 810 296615.310 274175.257 7.57% - 0s
0 0 274387.439 0 816 296615.310 274387.439 7.49% - 1s
0 0 274398.258 0 790 296615.310 274398.258 7.49% - 1s
0 0 274398.956 0 817 296615.310 274398.956 7.49% - 1s
0 0 274398.961 0 817 296615.310 274398.961 7.49% - 1s
0 0 275906.797 0 864 296615.310 275906.797 6.98% - 1s
0 0 276041.080 0 873 296615.310 276041.080 6.94% - 1s
0 0 276084.392 0 883 296615.310 276084.392 6.92% - 1s
0 0 276089.695 0 916 296615.310 276089.695 6.92% - 2s
0 0 276091.872 0 910 296615.310 276091.872 6.92% - 2s
0 0 276092.112 0 903 296615.310 276092.112 6.92% - 2s
0 0 276676.095 0 899 296615.310 276676.095 6.72% - 3s
0 0 276892.720 0 916 296615.310 276892.720 6.65% - 3s
0 0 276925.480 0 923 296615.310 276925.480 6.64% - 3s
0 0 276930.832 0 923 296615.310 276930.832 6.64% - 3s
0 0 276932.405 0 942 296615.310 276932.405 6.64% - 3s
0 0 276932.553 0 941 296615.310 276932.553 6.64% - 3s
0 0 277384.616 0 887 296615.310 277384.616 6.48% - 4s
0 2 277384.616 0 887 296615.310 277384.616 6.48% - 5s
165 174 278984.721 19 846 296615.310 277705.053 6.38% 183 10s
412 445 283287.283 42 766 296615.310 277705.053 6.38% 180 15s
H 529 538 296545.85094 277705.053 6.35% 169 16s
926 923 294734.649 104 560 296545.851 277724.118 6.35% 145 20s
1005 1013 295184.104 111 577 296545.851 277724.118 6.35% 140 25s
H 1155 1207 295517.37122 277724.118 6.02% 133 27s
1835 1856 283534.041 27 691 295517.371 277785.217 6.00% 132 30s
1973 1858 288853.542 142 522 295517.371 277785.217 6.00% 132 35s
1988 1868 283018.958 37 1049 295517.371 278764.332 5.67% 131 40s
1996 1874 279121.136 12 1139 295517.371 279121.136 5.55% 131 45s
2128 1974 280586.028 21 984 295517.371 279333.914 5.48% 153 50s
H 2191 1911 295012.16221 279333.914 5.31% 157 51s
H 2228 1850 294974.13520 279333.914 5.30% 160 52s
2295 1900 283737.679 31 822 294974.135 279333.914 5.30% 163 55s
H 2314 1820 294760.12095 279333.914 5.23% 164 55s
H 2358 1788 294759.96552 279333.914 5.23% 166 56s
2566 1910 288562.734 46 710 294759.966 279333.914 5.23% 180 60s
2847 2059 284637.848 39 826 294759.966 279333.914 5.23% 185 65s
2988 2120 285689.853 56 703 294759.966 279366.770 5.22% 188 70s
3341 2254 293006.677 103 678 294759.966 279374.393 5.22% 189 75s
3471 2296 293800.803 124 618 294759.966 279393.224 5.21% 190 80s
3675 2503 280204.404 24 942 294759.966 279393.224 5.21% 191 85s
3997 2570 284233.344 58 806 294759.966 279393.224 5.21% 193 90s
Cutting planes:
Gomory: 28
Cover: 1
Implied bound: 2
MIR: 494
StrongCG: 15
Flow cover: 325
Flow path: 2
GUB cover: 2
Zero half: 5
Network: 19
RLT: 13
Relax-and-lift: 45
BQP: 10
Explored 4005 nodes (785596 simplex iterations) in 90.06 seconds (104.80 work units)
Thread count was 16 (of 16 available processors)
Solution count 7: 294760 294760 294974 ... 296615
Time limit reached
Best objective 2.947599655209e+05, best bound 2.793932237341e+05, gap 5.2133%
WARNING: Loading a SolverResults object with an 'aborted' status, but
containing a solution
[51]:
SolutionInfo(runtime=90.0609998703003, bound=279393.2237340622, objective=294759.96552093467, relgap=0.05213306956293917, termination='maxTimeLimit')
[52]:
S210, G210 = solver.get_solution()
[53]:
svgplot(G210)
[53]:
[54]:
1 - G210.size(weight='length')/G210_ref.size(weight='length')
[54]:
0.02139847724499233
[55]:
with open('cazzaro_2022G_210_κ_7_radial_balanced_our.dill', 'wb') as outfile:
dill.dump(G210, outfile)