3.6.2 Cazzaro and Pisinger 2022 Fig. 6¶
This is used in the paper Flexible cable routing framework for wind farm collection system optimization.
[1]:
import pickle
from importlib.resources import files
from matplotlib import pyplot as plt
[2]:
from optiwindnet.interarraylib import G_from_S
from optiwindnet.svg import svgplot
from optiwindnet.plotting import pplot
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
[3]:
%config InlineBackend.figure_formats = ['svg']
plt.rcParams['svg.fonttype'] = 'none'
Reference solution¶
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
[4]:
G_ref = pickle.load(open('data/cazzaro_2022_paper_routeset.pkl', 'rb'))
[5]:
svgplot(G_ref)
[5]:
Start here¶
[6]:
solver = solver_factory('gurobi')
[7]:
L = L_from_yaml(files('optiwindnet.data') / 'Cazzaro-2022.yaml')
[8]:
svgplot(L)
[8]:
[9]:
P, A = make_planar_embedding(L)
[10]:
svgplot(A)
[10]:
[11]:
pplot(P, A);
Pre-solve¶
[12]:
Sʹ = hgs_cvrp(A, capacity=6, time_limit=0.5, balanced=True)
Sʹ.graph['solution_time']
[12]:
(0.18,)
[13]:
Gʹ = G_from_S(Sʹ, A)
svgplot(Gʹ)
[13]:
[14]:
Hʹ = PathFinder(Gʹ, planar=P, A=A).create_detours()
svgplot(Hʹ)
[14]:
[15]:
1 - Hʹ.size(weight='length')/G_ref.size(weight='length')
[15]:
0.013578500078660682
[16]:
solver.set_problem(
P, A,
capacity=6,
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
balanced=True,
),
warmstart=Sʹ,
)
[17]:
solver.solve(
mip_gap=0.005,
time_limit=35,
verbose=True,
options=dict(
mipfocus=2,
poolgap=0.015,
poolsearchmode=2,
poolsolutions=20
),
)
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 35
MIPGap 0.005
MIPFocus 2
PoolSolutions 20
PoolSearchMode 2
PoolGap 0.015
Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
Optimize a model with 1442 rows, 872 columns and 5342 nonzeros (Min)
Model fingerprint: 0x43b98d1c
Model has 436 linear objective coefficients
Variable types: 0 continuous, 872 integer (436 binary)
Coefficient statistics:
Matrix range [1e+00, 6e+00]
Objective range [6e-02, 1e+00]
Bounds range [1e+00, 6e+00]
RHS range [1e+00, 5e+01]
Loaded user MIP start with objective 9.67192
Presolve removed 192 rows and 0 columns
Presolve time: 0.01s
Presolved: 1250 rows, 872 columns, 4908 nonzeros
Variable types: 0 continuous, 872 integer (436 binary)
Root relaxation presolved: 1248 rows, 872 columns, 4876 nonzeros
Root relaxation: objective 8.956774e+00, 983 iterations, 0.02 seconds (0.02 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 8.95677 0 127 9.67192 8.95677 7.39% - 0s
0 0 9.22792 0 187 9.67192 9.22792 4.59% - 0s
0 0 9.29995 0 204 9.67192 9.29995 3.85% - 0s
0 0 9.29995 0 215 9.67192 9.29995 3.85% - 0s
0 0 9.30038 0 212 9.67192 9.30038 3.84% - 0s
0 0 9.30049 0 223 9.67192 9.30049 3.84% - 0s
0 0 9.33383 0 248 9.67192 9.33383 3.50% - 0s
0 0 9.33564 0 253 9.67192 9.33564 3.48% - 0s
0 0 9.33577 0 257 9.67192 9.33577 3.48% - 0s
0 0 9.37648 0 260 9.67192 9.37648 3.05% - 0s
0 0 9.37648 0 264 9.67192 9.37648 3.05% - 0s
0 0 9.37648 0 268 9.67192 9.37648 3.05% - 0s
0 0 9.38106 0 276 9.67192 9.38106 3.01% - 0s
0 0 9.39460 0 267 9.67192 9.39460 2.87% - 0s
0 0 9.39772 0 261 9.67192 9.39772 2.84% - 0s
0 0 9.39817 0 264 9.67192 9.39817 2.83% - 0s
0 0 9.39825 0 262 9.67192 9.39825 2.83% - 0s
0 0 9.40620 0 256 9.67192 9.40620 2.75% - 1s
0 0 9.40722 0 280 9.67192 9.40722 2.74% - 1s
0 0 9.40741 0 276 9.67192 9.40741 2.73% - 1s
0 0 9.42158 0 282 9.67192 9.42158 2.59% - 1s
0 0 9.42158 0 266 9.67192 9.42158 2.59% - 1s
0 0 9.42158 0 274 9.67192 9.42158 2.59% - 1s
0 0 9.42932 0 243 9.67192 9.42932 2.51% - 1s
0 0 9.43204 0 250 9.67192 9.43204 2.48% - 1s
0 0 9.43222 0 252 9.67192 9.43222 2.48% - 1s
0 0 9.43557 0 258 9.67192 9.43557 2.44% - 1s
0 0 9.43647 0 258 9.67192 9.43647 2.43% - 1s
0 0 9.43656 0 254 9.67192 9.43656 2.43% - 1s
0 0 9.43947 0 270 9.67192 9.43947 2.40% - 1s
0 0 9.44075 0 274 9.67192 9.44075 2.39% - 2s
0 0 9.44088 0 274 9.67192 9.44088 2.39% - 2s
0 0 9.44581 0 261 9.67192 9.44581 2.34% - 2s
0 0 9.44591 0 275 9.67192 9.44591 2.34% - 2s
0 0 9.44855 0 260 9.67192 9.44855 2.31% - 2s
0 0 9.44869 0 260 9.67192 9.44869 2.31% - 2s
0 0 9.44869 0 260 9.67192 9.44869 2.31% - 2s
0 2 9.44869 0 260 9.67192 9.44869 2.31% - 2s
1576 1323 9.67192 19 260 9.67192 9.51769 1.59% 96.3 5s
2409 1701 9.72112 27 162 9.67192 9.54386 1.32% 98.8 10s
9832 6289 9.72235 48 202 9.67192 9.62786 0.46% 85.9 15s
Optimal solution found at node 18498 - now completing solution pool...
Nodes | Current Node | Pool Obj. Bounds | Work
| | Worst |
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
18498 11126 cutoff 30 9.80722 9.67305 1.37% 82.9 19s
20712 10704 9.74505 51 102 9.79341 9.67622 1.20% 80.0 20s
Cutting planes:
Gomory: 24
Lift-and-project: 8
Cover: 53
Implied bound: 10
Projected implied bound: 3
Clique: 3
MIR: 203
StrongCG: 5
Flow cover: 219
Flow path: 5
Inf proof: 2
Zero half: 89
Network: 22
RLT: 7
Relax-and-lift: 20
Explored 30072 nodes (2168766 simplex iterations) in 22.91 seconds (26.36 work units)
Thread count was 16 (of 16 available processors)
Solution count 20: 9.67192 9.68346 9.69748 ... 9.73464
No other solutions better than 9.73464
Optimal solution found (tolerance 5.00e-03)
Best objective 9.671920168636e+00, best bound 9.671920168636e+00, gap 0.0000%
[17]:
SolutionInfo(runtime=22.922324180603027, bound=9.671920168635916, objective=9.671920168635916, relgap=0.0, termination='optimal')
[18]:
S, G = solver.get_solution()
svgplot(G)
[18]:
[19]:
1 - G.size(weight='length')/G_ref.size(weight='length')
[19]:
0.024457285866890444
[20]:
with open('cazzaro_2022_comparison_κ_6_radial_balanced.pkl', 'wb') as outfile:
pickle.dump(G, outfile)