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 dill
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_multiroot
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 = dill.load(open('data/cazzaro_2022_paper_routeset.dill', '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_multiroot(A, capacity=6, time_limit=0.5, balanced=True)
[13]:
Sʹ.graph['solution_time']
[13]:
(0.04,)
[14]:
Gʹ = G_from_S(Sʹ, A)
[15]:
svgplot(Gʹ)
[15]:
[16]:
Hʹ = PathFinder(Gʹ, planar=P, A=A).create_detours()
[17]:
svgplot(Hʹ)
[17]:
[18]:
1 - Hʹ.size(weight='length')/G_ref.size(weight='length')
[18]:
0.013578500078660682
[21]:
solver.set_problem(
P, A,
capacity=6,
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
balanced=True,
),
warmstart=Sʹ,
)
[69]:
solver.solve(
mip_gap=0.005,
time_limit=35,
verbose=True,
options=dict(
mipfocus=2,
poolgap=0.015,
poolsearchmode=2,
poolsolutions=20
),
)
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 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 1443 rows, 872 columns and 5392 nonzeros
Model fingerprint: 0xc18dc203
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.69831
Presolve removed 193 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.997354e+00, 885 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.99735 0 145 9.69831 8.99735 7.23% - 0s
0 0 9.20198 0 217 9.69831 9.20198 5.12% - 0s
0 0 9.28837 0 212 9.69831 9.28837 4.23% - 0s
0 0 9.29008 0 216 9.69831 9.29008 4.21% - 0s
0 0 9.29008 0 223 9.69831 9.29008 4.21% - 0s
0 0 9.29008 0 216 9.69831 9.29008 4.21% - 0s
0 0 9.32004 0 234 9.69831 9.32004 3.90% - 0s
0 0 9.32208 0 246 9.69831 9.32208 3.88% - 0s
0 0 9.32273 0 251 9.69831 9.32273 3.87% - 0s
0 0 9.32298 0 248 9.69831 9.32298 3.87% - 0s
0 0 9.32298 0 248 9.69831 9.32298 3.87% - 0s
0 0 9.33646 0 262 9.69831 9.33646 3.73% - 1s
0 0 9.34009 0 275 9.69831 9.34009 3.69% - 1s
0 0 9.34023 0 279 9.69831 9.34023 3.69% - 1s
0 0 9.35065 0 282 9.69831 9.35065 3.58% - 1s
0 0 9.35299 0 274 9.69831 9.35299 3.56% - 1s
0 0 9.35345 0 285 9.69831 9.35345 3.56% - 1s
0 0 9.35389 0 294 9.69831 9.35389 3.55% - 1s
0 0 9.35408 0 287 9.69831 9.35408 3.55% - 1s
0 0 9.36799 0 273 9.69831 9.36799 3.41% - 1s
0 0 9.37233 0 295 9.69831 9.37233 3.36% - 1s
0 0 9.37373 0 286 9.69831 9.37373 3.35% - 1s
0 0 9.37387 0 292 9.69831 9.37387 3.35% - 1s
0 0 9.38179 0 296 9.69831 9.38179 3.26% - 2s
0 0 9.38312 0 308 9.69831 9.38312 3.25% - 2s
0 0 9.38330 0 306 9.69831 9.38330 3.25% - 2s
0 0 9.39036 0 276 9.69831 9.39036 3.18% - 2s
0 0 9.39317 0 300 9.69831 9.39317 3.15% - 2s
0 0 9.39347 0 302 9.69831 9.39347 3.14% - 2s
0 0 9.39351 0 308 9.69831 9.39351 3.14% - 2s
0 0 9.40032 0 288 9.69831 9.40032 3.07% - 2s
0 0 9.40364 0 294 9.69831 9.40364 3.04% - 2s
0 0 9.40401 0 310 9.69831 9.40401 3.03% - 2s
0 0 9.40417 0 314 9.69831 9.40417 3.03% - 2s
0 0 9.41249 0 298 9.69831 9.41249 2.95% - 3s
0 0 9.41372 0 296 9.69831 9.41372 2.93% - 3s
0 0 9.41379 0 300 9.69831 9.41379 2.93% - 3s
0 0 9.41764 0 294 9.69831 9.41764 2.89% - 3s
0 0 9.41823 0 283 9.69831 9.41823 2.89% - 3s
0 0 9.41841 0 295 9.69831 9.41841 2.89% - 3s
0 0 9.42136 0 292 9.69831 9.42136 2.86% - 3s
0 0 9.42137 0 292 9.69831 9.42137 2.86% - 3s
0 2 9.42142 0 292 9.69831 9.42142 2.85% - 4s
356 362 9.81496 42 188 9.69831 9.43757 2.69% 122 5s
1676 1351 9.66313 23 297 9.69831 9.48726 2.18% 109 10s
2237 1674 9.69656 23 174 9.69831 9.53857 1.65% 115 15s
7482 4464 cutoff 27 9.69831 9.61913 0.82% 89.6 20s
13194 8350 infeasible 30 9.69831 9.65352 0.46% 85.8 25s
19186 12363 cutoff 36 9.69831 9.67969 0.19% 83.4 30s
Optimal solution found at node 25155 - now completing solution pool...
Nodes | Current Node | Pool Obj. Bounds | Work
| | Worst |
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
25155 12577 9.79601 22 232 9.80717 9.70040 1.09% 81.4 35s
Cutting planes:
Gomory: 19
Lift-and-project: 19
Cover: 60
Implied bound: 11
MIR: 280
StrongCG: 14
Flow cover: 272
Flow path: 3
GUB cover: 3
Inf proof: 5
Zero half: 67
Network: 10
RLT: 8
Relax-and-lift: 29
BQP: 4
Explored 26394 nodes (2117513 simplex iterations) in 35.08 seconds (33.93 work units)
Thread count was 16 (of 16 available processors)
Solution count 20: 9.69831 9.70305 9.72387 ... 9.78342
No other solutions better than 9.70222
Time limit reached
Best objective 9.698310786396e+00, best bound 9.698310786396e+00, gap 0.0000%
WARNING: Loading a SolverResults object with an 'aborted' status, but
containing a solution
[69]:
SolutionInfo(runtime=35.08200001716614, bound=9.698310786396384, objective=9.698310786396384, relgap=0.0, termination='maxTimeLimit')
[70]:
S, G = solver.get_solution()
[71]:
svgplot(G)
[71]:
[72]:
1 - G.size(weight='length')/G_ref.size(weight='length')
[72]:
0.017546306686529123
[73]:
with open('cazzaro_2022_comparison_κ_6_radial_balanced.dill', 'wb') as outfile:
dill.dump(G, outfile)