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 pickle
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_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 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 = pickle.load(open('data/cazzaro_2022G_140_paper_routeset.pkl', 'rb'))
[4]:
svgplot(G140_ref)
[4]:
[5]:
G210_ref = pickle.load(open('data/cazzaro_2022G_210_paper_routeset.pkl', 'rb'))
[6]:
svgplot(G210_ref)
[6]:
Start here¶
Instantiate solver¶
[7]:
solver = solver_factory('gurobi')
G-140, κ = 6¶
[8]:
L140 = L_from_yaml(files('optiwindnet.data') / 'Cazzaro-2022G-140.yaml')
[9]:
svgplot(L140)
[9]:
[10]:
P, A = make_planar_embedding(L140)
A_norm = as_normalized(A)
[11]:
Sʹ = hgs_cvrp(A_norm, capacity=6, time_limit=0.5, balanced=True)
Sʹ.graph['solution_time']
[11]:
(0.05, 0.03, 0.05)
[12]:
Gʹ = G_from_S(Sʹ, A)
svgplot(Gʹ)
[12]:
[13]:
[[Sʹ[r][n]['load'] for n in Sʹ[r]] for r in range(-3, 0)]
[13]:
[[6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6], [5, 5, 5, 6, 6, 6, 5, 6]]
[14]:
Hʹ = PathFinder(Gʹ, planar=P, A=A, branched=False).create_detours()
svgplot(Hʹ)
[14]:
[15]:
Hʹ.size(weight='length')/G140_ref.size(weight='length') - 1
[15]:
0.01422305639439081
[16]:
solver.set_problem(
P, A,
capacity=Sʹ.graph['capacity'],
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
balanced=True,
),
warmstart=Sʹ,
)
[17]:
solver.solve(
mip_gap=0.005,
time_limit=10,
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 10
MIPGap 0.005
MIPFocus 1
Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
Optimize a model with 5391 rows, 3328 columns and 20386 nonzeros (Min)
Model fingerprint: 0x6f32ce01
Model has 1664 linear objective coefficients
Variable types: 0 continuous, 3328 integer (1664 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 950 rows and 0 columns
Presolve time: 0.03s
Presolved: 4441 rows, 3328 columns, 18066 nonzeros
Variable types: 0 continuous, 3328 integer (1664 binary)
Root relaxation: objective 2.198935e+05, 4502 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 219893.521 0 306 243297.915 219893.521 9.62% - 0s
H 0 0 242528.56393 219893.521 9.33% - 0s
0 0 223839.736 0 481 242528.564 223839.736 7.71% - 0s
0 0 224054.813 0 518 242528.564 224054.813 7.62% - 0s
0 0 224059.847 0 508 242528.564 224059.847 7.62% - 0s
0 0 224059.847 0 508 242528.564 224059.847 7.62% - 0s
0 0 225656.208 0 592 242528.564 225656.208 6.96% - 0s
0 0 225859.435 0 558 242528.564 225859.435 6.87% - 0s
0 0 225874.645 0 578 242528.564 225874.645 6.87% - 0s
H 0 0 241364.06683 225877.021 6.42% - 0s
0 0 225877.021 0 572 241364.067 225877.021 6.42% - 0s
0 0 225877.354 0 580 241364.067 225877.354 6.42% - 0s
H 0 0 240654.84015 226642.111 5.82% - 1s
H 0 0 238169.24426 226642.111 4.84% - 1s
0 0 226642.111 0 613 238169.244 226642.111 4.84% - 1s
0 0 226881.597 0 597 238169.244 226881.597 4.74% - 1s
0 0 226962.305 0 655 238169.244 226962.305 4.71% - 1s
0 0 226988.589 0 676 238169.244 226988.589 4.69% - 1s
0 0 226993.066 0 664 238169.244 226993.066 4.69% - 1s
0 0 226996.451 0 657 238169.244 226996.451 4.69% - 1s
0 0 226996.736 0 663 238169.244 226996.736 4.69% - 1s
0 0 227218.477 0 645 238169.244 227218.477 4.60% - 1s
0 0 227366.589 0 650 238169.244 227366.589 4.54% - 2s
0 0 227428.497 0 663 238169.244 227428.497 4.51% - 2s
0 0 227440.990 0 681 238169.244 227440.990 4.50% - 2s
H 0 0 237931.18714 227449.457 4.41% - 2s
0 0 227449.457 0 678 237931.187 227449.457 4.41% - 2s
0 0 227451.057 0 670 237931.187 227451.057 4.40% - 2s
0 0 227452.677 0 682 237931.187 227452.677 4.40% - 2s
0 0 227453.197 0 686 237931.187 227453.197 4.40% - 2s
H 0 0 237843.95550 227453.197 4.37% - 2s
0 0 227678.369 0 667 237843.955 227678.369 4.27% - 2s
0 0 227678.369 0 667 237843.955 227678.369 4.27% - 2s
H 0 0 237646.00024 227678.380 4.19% - 3s
H 0 0 236937.28941 227678.380 3.91% - 4s
H 0 0 236890.07385 227678.380 3.89% - 4s
0 2 227678.380 0 667 236890.074 227678.380 3.89% - 7s
H 85 88 236871.54789 227773.165 3.84% 195 8s
H 103 112 236706.80469 227773.165 3.77% 188 9s
178 186 229698.254 20 540 236706.805 227773.165 3.77% 185 10s
Cutting planes:
Learned: 1
Gomory: 38
Cover: 1
Clique: 1
MIR: 281
StrongCG: 7
Flow cover: 90
Flow path: 5
GUB cover: 5
Zero half: 2
Mod-K: 3
Network: 37
RLT: 5
Relax-and-lift: 5
Explored 185 nodes (44626 simplex iterations) in 10.01 seconds (11.59 work units)
Thread count was 16 (of 16 available processors)
Solution count 10: 236707 236872 236890 ... 241364
Time limit reached
Best objective 2.367068046913e+05, best bound 2.277731648146e+05, gap 3.7741%
[17]:
SolutionInfo(runtime=10.011543989181519, bound=227773.16481460136, objective=236706.80469130888, relgap=0.03774137329240679, termination='maxTimeLimit')
[18]:
S140, G140 = solver.get_solution()
svgplot(G140)
[18]:
[19]:
[[G140[r][n]['load'] for n in G140[r]] for r in range(-3, 0)]
[19]:
[[6, 6, 6, 6, 6, 6, 6, 5, 6, 6], [6, 6, 6, 5, 5, 6], [5, 6, 6, 6, 6, 6, 6, 6]]
[20]:
1 - G140.size(weight='length')/G140_ref.size(weight='length')
[20]:
0.020539760123712503
[21]:
pickle.dump(G140, open('cazzaro_2022G_140_κ_6_radial_balanced_our.pkl', 'wb'))
G-210, κ = 7¶
[22]:
L210 = L_from_yaml(files('optiwindnet.data') / 'Cazzaro-2022G-210.yaml')
[23]:
P, A = make_planar_embedding(L210)
A_norm = as_normalized(A)
[24]:
svgplot(L210)
[24]:
[25]:
Sʹ = hgs_cvrp(A_norm, capacity=7, time_limit=1, balanced=True)
Sʹ.graph['solution_time']
[25]:
(0.27, 0.22, 0.26)
[26]:
Gʹ = G_from_S(Sʹ, A)
Hʹ = PathFinder(Gʹ, planar=P, A=A, branched=False).create_detours()
svgplot(Hʹ)
[26]:
[27]:
1- Hʹ.size(weight='length')/G210_ref.size(weight='length')
[27]:
0.015090421048965408
Solve the balanced MILP model¶
[28]:
solver.set_problem(
P, A,
capacity=Sʹ.graph['capacity'],
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
balanced=True,
),
warmstart=Sʹ,
)
[29]:
solver.solve(
mip_gap=0.005,
time_limit=95,
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 95
MIPGap 0.005
MIPFocus 1
Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
Optimize a model with 7784 rows, 5212 columns and 30812 nonzeros (Min)
Model fingerprint: 0x06b5df69
Model has 2606 linear objective coefficients
Variable types: 0 continuous, 5212 integer (2606 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 296625
Presolve removed 860 rows and 0 columns
Presolve time: 0.04s
Presolved: 6924 rows, 5212 columns, 28462 nonzeros
Variable types: 0 continuous, 5212 integer (2606 binary)
Root relaxation: objective 2.696831e+05, 6305 iterations, 0.13 seconds (0.20 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 269683.061 0 526 296624.904 269683.061 9.08% - 0s
0 0 274396.792 0 768 296624.904 274396.792 7.49% - 0s
0 0 274596.625 0 837 296624.904 274596.625 7.43% - 0s
0 0 274617.021 0 799 296624.904 274617.021 7.42% - 0s
0 0 274618.331 0 801 296624.904 274618.331 7.42% - 0s
0 0 275882.386 0 916 296624.904 275882.386 6.99% - 1s
0 0 276186.363 0 906 296624.904 276186.363 6.89% - 1s
0 0 276230.355 0 912 296624.904 276230.355 6.88% - 1s
0 0 276244.314 0 919 296624.904 276244.314 6.87% - 1s
0 0 276245.906 0 917 296624.904 276245.906 6.87% - 1s
0 0 276246.006 0 923 296624.904 276246.006 6.87% - 1s
0 0 277065.336 0 929 296624.904 277065.336 6.59% - 2s
0 0 277333.175 0 902 296624.904 277333.175 6.50% - 2s
0 0 277387.621 0 947 296624.904 277387.621 6.49% - 2s
0 0 277398.049 0 959 296624.904 277398.049 6.48% - 2s
0 0 277404.824 0 956 296624.904 277404.824 6.48% - 2s
0 0 277406.776 0 965 296624.904 277406.776 6.48% - 2s
0 0 277408.942 0 950 296624.904 277408.942 6.48% - 2s
0 0 277409.057 0 960 296624.904 277409.057 6.48% - 2s
0 0 277965.185 0 1017 296624.904 277965.185 6.29% - 3s
0 0 278135.760 0 977 296624.904 278135.760 6.23% - 3s
0 0 278195.212 0 1003 296624.904 278195.212 6.21% - 3s
0 0 278212.620 0 1023 296624.904 278212.620 6.21% - 4s
0 0 278225.864 0 1021 296624.904 278225.864 6.20% - 4s
0 0 278229.499 0 1026 296624.904 278229.499 6.20% - 4s
0 0 278230.006 0 1029 296624.904 278230.006 6.20% - 4s
0 0 278414.005 0 1046 296624.904 278414.005 6.14% - 4s
0 0 278414.005 0 1041 296624.904 278414.005 6.14% - 4s
0 2 278414.412 0 1041 296624.904 278414.412 6.14% - 13s
45 54 278794.049 7 1054 296624.904 278658.573 6.06% 250 15s
258 276 279708.627 20 969 296624.904 278658.573 6.06% 184 20s
704 749 282652.138 36 852 296624.904 278658.573 6.06% 165 25s
1201 1179 279105.221 6 961 296624.904 278738.949 6.03% 152 30s
1736 1649 281780.687 50 1041 296624.904 278744.559 6.03% 152 40s
1750 1658 293043.807 122 1080 296624.904 279044.479 5.93% 151 45s
1769 1671 294634.876 119 1089 296624.904 279618.149 5.73% 149 50s
1770 1672 287123.811 33 1089 296624.904 279618.149 5.73% 149 63s
1793 1710 279925.674 20 1118 296624.904 279836.205 5.66% 165 65s
2036 1864 281237.190 36 905 296624.904 279836.205 5.66% 182 70s
2131 1923 281527.389 40 876 296624.904 279836.205 5.66% 188 75s
2185 1959 282238.081 42 885 296624.904 279836.205 5.66% 190 80s
2261 2026 282648.984 45 820 296624.904 279836.205 5.66% 195 85s
H 2374 2015 296588.39354 279836.205 5.65% 199 88s
H 2402 1984 296273.10635 279836.205 5.55% 200 89s
2473 2018 283938.586 50 808 296273.106 279836.205 5.55% 201 90s
H 2644 1972 296185.86881 279877.733 5.51% 202 91s
H 2688 1906 296121.48191 279892.671 5.48% 202 92s
H 2836 1903 296105.07778 279897.234 5.47% 202 93s
3070 2029 infeasible 97 296105.078 279897.234 5.47% 201 95s
Cutting planes:
Gomory: 37
Cover: 1
Implied bound: 1
Clique: 5
MIR: 429
StrongCG: 14
Flow cover: 245
Flow path: 4
GUB cover: 2
Zero half: 6
Network: 20
RLT: 15
Relax-and-lift: 40
BQP: 4
Explored 3071 nodes (633228 simplex iterations) in 95.01 seconds (129.92 work units)
Thread count was 16 (of 16 available processors)
Solution count 6: 296105 296121 296186 ... 296625
Time limit reached
Best objective 2.961050777801e+05, best bound 2.798972338897e+05, gap 5.4737%
[29]:
SolutionInfo(runtime=95.01063799858093, bound=279897.23388969863, objective=296105.077780097, relgap=0.054736798206598714, termination='maxTimeLimit')
[30]:
S210, G210 = solver.get_solution()
svgplot(G210)
[30]:
[31]:
1 - G210.size(weight='length')/G210_ref.size(weight='length')
[31]:
0.016985200900690445
[32]:
pickle.dump(G210, open('cazzaro_2022G_210_κ_7_radial_balanced_our.pkl', 'wb'))