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¶
[23]:
L140 = L_from_yaml(files('optiwindnet.data') / 'Cazzaro-2022G-140.yaml')
[24]:
svgplot(L140)
[24]:
[25]:
P, A = make_planar_embedding(L140)
A_norm = as_normalized(A)
[26]:
Sʹ = hgs_multiroot(A_norm, capacity=6, time_limit=0.5, balanced=True)
[27]:
Sʹ.graph['solution_time']
[27]:
(0.25, 0.04, 0.06)
[28]:
Gʹ = G_from_S(Sʹ, A)
[29]:
svgplot(Gʹ)
[29]:
[30]:
[[Sʹ[r][n]['load'] for n in Sʹ[r]] for r in range(-3, 0)]
[30]:
[[6, 6, 6, 6, 6, 6, 6, 6, 6], [6, 6, 6, 6, 6, 6, 6], [5, 5, 5, 6, 6, 6, 5, 6]]
[31]:
Hʹ = PathFinder(Gʹ, planar=P, A=A, branched=False).create_detours()
[32]:
svgplot(Hʹ)
[32]:
[33]:
Hʹ.size(weight='length')/G140_ref.size(weight='length') - 1
[33]:
0.01422305639439081
[34]:
solver.set_problem(
P, A,
capacity=Sʹ.graph['capacity'],
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
balanced=True,
),
warmstart=Sʹ,
)
[35]:
solver.set_problem(
P, A,
capacity=Sʹ.graph['capacity'],
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
balanced=True,
),
warmstart=Sʹ,
)
[36]:
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.3 build v12.0.3rc0 (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 5387 rows, 3324 columns and 20784 nonzeros
Model fingerprint: 0xb9f7ec7f
Variable types: 0 continuous, 3324 integer (1662 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 951 rows and 0 columns
Presolve time: 0.03s
Presolved: 4436 rows, 3324 columns, 18044 nonzeros
Variable types: 0 continuous, 3324 integer (1662 binary)
Root relaxation: objective 2.199121e+05, 4222 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.125 0 303 243297.915 219912.125 9.61% - 0s
H 0 0 242528.56393 219912.125 9.33% - 0s
0 0 223993.254 0 506 242528.564 223993.254 7.64% - 0s
0 0 224084.717 0 519 242528.564 224084.717 7.60% - 0s
0 0 224095.074 0 525 242528.564 224095.074 7.60% - 0s
0 0 224096.578 0 528 242528.564 224096.578 7.60% - 0s
0 0 224096.617 0 515 242528.564 224096.617 7.60% - 0s
H 0 0 241364.06683 224096.617 7.15% - 0s
0 0 225370.560 0 550 241364.067 225370.560 6.63% - 0s
0 0 225565.142 0 604 241364.067 225565.142 6.55% - 0s
0 0 225615.031 0 587 241364.067 225615.031 6.53% - 0s
0 0 225617.987 0 583 241364.067 225617.987 6.52% - 0s
0 0 225618.643 0 580 241364.067 225618.643 6.52% - 0s
0 0 225618.746 0 594 241364.067 225618.746 6.52% - 0s
H 0 0 241021.97105 225618.746 6.39% - 1s
H 0 0 239068.72253 225618.746 5.63% - 1s
0 0 226405.872 0 646 239068.723 226405.872 5.30% - 1s
H 0 0 238724.85414 226405.872 5.16% - 1s
0 0 226578.755 0 659 238724.854 226578.755 5.09% - 1s
0 0 226623.664 0 657 238724.854 226623.664 5.07% - 1s
0 0 226628.548 0 655 238724.854 226628.548 5.07% - 1s
0 0 226630.495 0 666 238724.854 226630.495 5.07% - 1s
0 0 226630.629 0 666 238724.854 226630.629 5.07% - 1s
0 0 227010.487 0 646 238724.854 227010.487 4.91% - 2s
0 2 227010.678 0 646 238724.854 227010.678 4.91% - 3s
H 1 4 238048.94350 227010.973 4.64% 116 3s
H 27 33 237982.78645 227175.192 4.54% 275 3s
H 44 52 237795.06576 227175.192 4.47% 229 4s
94 107 227623.758 13 644 237795.066 227175.192 4.47% 195 5s
H 124 133 237725.29284 227175.192 4.44% 202 5s
H 232 241 237544.57690 227175.192 4.37% 175 6s
H 318 322 237520.99301 227175.192 4.36% 172 7s
H 381 403 237501.96625 227175.192 4.35% 164 7s
H 398 403 237015.32242 227175.192 4.15% 162 7s
H 406 408 236637.03177 227175.192 4.00% 161 8s
H 485 444 236462.08620 227175.192 3.93% 156 8s
H 548 493 236406.97459 227175.192 3.91% 158 9s
H 551 493 236375.56172 227175.192 3.89% 157 9s
579 521 235210.933 56 447 236375.562 227204.064 3.88% 158 10s
Cutting planes:
Gomory: 33
Cover: 3
Implied bound: 6
MIR: 286
StrongCG: 7
Flow cover: 86
Flow path: 12
GUB cover: 4
Zero half: 4
Network: 44
RLT: 8
Relax-and-lift: 3
Explored 587 nodes (100683 simplex iterations) in 10.04 seconds (11.15 work units)
Thread count was 16 (of 16 available processors)
Solution count 10: 236376 236407 236462 ... 237795
Time limit reached
Best objective 2.363755617238e+05, best bound 2.272041605162e+05, gap 3.8800%
WARNING: Loading a SolverResults object with an 'aborted' status, but
containing a solution
[36]:
SolutionInfo(runtime=10.044999837875366, bound=227204.1605161552, objective=236375.5617237814, relgap=0.038800124432252, termination='maxTimeLimit')
[37]:
S140, G140 = solver.get_solution()
[38]:
[[G140[r][n]['load'] for n in G140[r]] for r in range(-3, 0)]
[38]:
[[6, 6, 6, 6, 6, 6, 6, 5, 6, 6], [6, 6, 6, 5, 5, 6], [5, 6, 6, 6, 6, 6, 6, 6]]
[39]:
1 - G140.size(weight='length')/G140_ref.size(weight='length')
[39]:
0.020828468287038326
[40]:
svgplot(G140)
[40]:
[41]:
with open('cazzaro_2022G_140_κ_6_radial_balanced_our.dill', 'wb') as outfile:
dill.dump(G140, outfile)
G-210, κ = 7¶
[8]:
L210 = L_from_yaml(files('optiwindnet.data') / 'Cazzaro-2022G-210.yaml')
[9]:
P, A = make_planar_embedding(L210)
A_norm = as_normalized(A)
[10]:
svgplot(L210)
[10]:
[11]:
Sʹ = hgs_multiroot(A_norm, capacity=7, time_limit=0.5)
[12]:
Sʹ.graph['solution_time']
[12]:
(0.36, 0.29, 0.35)
[13]:
Gʹ = G_from_S(Sʹ, A)
[14]:
Hʹ = PathFinder(Gʹ, planar=P, A=A, branched=False).create_detours()
[15]:
svgplot(Hʹ)
[15]:
[16]:
1- Hʹ.size(weight='length')/G210_ref.size(weight='length')
[16]:
0.01517110172331404
Solve the balanced MILP model¶
90 s Gurobi¶
[17]:
solver.set_problem(
P, A,
capacity=Sʹ.graph['capacity'],
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
balanced=True,
),
warmstart=Sʹ,
)
[18]:
solver.solve(
mip_gap=0.005,
time_limit=90,
verbose=True,
options=dict(
RINS=100,
CutPasses=4,
VarBranch=1,
),
)
Set parameter OutputFlag to value 1
Gurobi Optimizer version 12.0.3 build v12.0.3rc0 (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 7781 rows, 5208 columns and 31424 nonzeros
Model fingerprint: 0xc1a9e0ab
Variable types: 0 continuous, 5208 integer (2604 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 863 rows and 0 columns
Presolve time: 0.04s
Presolved: 6918 rows, 5208 columns, 28440 nonzeros
Variable types: 0 continuous, 5208 integer (2604 binary)
Root relaxation: objective 2.696831e+05, 6139 iterations, 0.18 seconds (0.22 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 274087.161 0 805 296615.310 274087.161 7.60% - 0s
0 0 274277.712 0 803 296615.310 274277.712 7.53% - 0s
0 0 274284.710 0 809 296615.310 274284.710 7.53% - 0s
0 0 274285.474 0 815 296615.310 274285.474 7.53% - 0s
0 0 274285.481 0 816 296615.310 274285.481 7.53% - 0s
0 0 275691.998 0 835 296615.310 275691.998 7.05% - 1s
0 0 275886.525 0 894 296615.310 275886.525 6.99% - 1s
0 0 275932.314 0 890 296615.310 275932.314 6.97% - 1s
0 0 275933.479 0 902 296615.310 275933.479 6.97% - 1s
0 0 275935.879 0 904 296615.310 275935.879 6.97% - 1s
0 0 275935.984 0 906 296615.310 275935.984 6.97% - 1s
0 0 276570.974 0 956 296615.310 276570.974 6.76% - 2s
0 0 276728.565 0 951 296615.310 276728.565 6.70% - 2s
0 0 276765.275 0 964 296615.310 276765.275 6.69% - 2s
0 0 276776.615 0 970 296615.310 276776.615 6.69% - 2s
0 0 276778.102 0 965 296615.310 276778.102 6.69% - 2s
0 0 276778.384 0 964 296615.310 276778.384 6.69% - 2s
0 0 277216.062 0 997 296615.310 277216.062 6.54% - 3s
0 2 277216.062 0 997 296615.310 277216.062 6.54% - 4s
3 8 277419.281 2 987 296615.310 277232.637 6.53% 269 5s
225 236 279419.543 19 829 296615.310 277512.867 6.44% 188 10s
H 310 318 296468.36423 277512.867 6.39% 184 12s
H 365 375 296451.16816 277512.867 6.39% 182 12s
537 558 283321.195 35 730 296451.168 277512.867 6.39% 166 15s
H 556 558 295890.54091 277512.867 6.21% 163 15s
H 713 715 295715.35272 277531.088 6.15% 149 16s
H 841 840 295640.25910 277531.088 6.13% 142 17s
1101 1143 292691.608 97 575 295640.259 277531.088 6.13% 133 20s
1544 1472 282925.814 42 997 295640.259 277531.088 6.13% 133 25s
1554 1479 278730.052 11 1099 295640.259 278159.027 5.91% 132 30s
1573 1492 279334.519 17 522 295640.259 279334.519 5.52% 142 36s
1588 1502 292077.093 72 1094 295640.259 279430.626 5.48% 141 40s
1598 1514 279576.495 24 1073 295640.259 279535.653 5.45% 150 45s
1809 1663 281195.474 40 920 295640.259 279623.625 5.42% 165 50s
1996 1791 284879.411 53 763 295640.259 279623.625 5.42% 174 55s
2119 1862 287529.114 61 736 295640.259 279623.625 5.42% 175 60s
H 2317 1912 294602.63748 279623.625 5.08% 176 64s
2415 1977 288849.354 70 675 294602.637 279623.625 5.08% 176 65s
2772 2122 279881.900 30 954 294602.637 279645.050 5.08% 172 70s
H 2849 2046 294442.28087 279655.211 5.02% 174 72s
2894 2080 280290.797 37 930 294442.281 279655.211 5.02% 173 75s
H 2924 2005 294222.20524 279655.211 4.95% 173 76s
3054 2070 281748.152 50 900 294222.205 279655.211 4.95% 174 80s
H 3133 2101 293936.54134 279655.211 4.86% 175 83s
3336 2177 285167.561 61 773 293936.541 279655.211 4.86% 175 85s
3376 2199 287845.909 68 739 293936.541 279655.211 4.86% 176 90s
Cutting planes:
Gomory: 19
Cover: 3
Implied bound: 1
Clique: 2
MIR: 397
StrongCG: 11
Flow cover: 259
Flow path: 4
Zero half: 5
Network: 12
RLT: 11
Relax-and-lift: 40
BQP: 11
Explored 3384 nodes (605488 simplex iterations) in 90.05 seconds (114.55 work units)
Thread count was 16 (of 16 available processors)
Solution count 10: 293937 294222 294442 ... 296615
Time limit reached
Best objective 2.939365413391e+05, best bound 2.796552111162e+05, gap 4.8586%
WARNING: Loading a SolverResults object with an 'aborted' status, but
containing a solution
[18]:
SolutionInfo(runtime=90.06900000572205, bound=279655.2111162467, objective=293936.5413391452, relgap=0.048586440317471946, termination='maxTimeLimit')
[19]:
S210, G210 = solver.get_solution()
[20]:
svgplot(G210)
[20]:
[21]:
1 - G210.size(weight='length')/G210_ref.size(weight='length')
[21]:
0.024698115350317407
[22]:
with open('cazzaro_2022G_210_κ_7_radial_balanced_our.dill', 'wb') as outfile:
dill.dump(G210, outfile)