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.18,)
[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
[19]:
solver.set_problem(
P, A,
capacity=6,
model_options=ModelOptions(
topology="radial",
feeder_route="segmented",
feeder_limit="minimum",
balanced=True,
),
warmstart=Sʹ,
)
[20]:
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: 0xe1034d1b
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 193 rows and 0 columns
Presolve time: 0.02s
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, 977 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.18053 0 168 9.67192 9.18053 5.08% - 0s
0 0 9.18100 0 168 9.67192 9.18100 5.08% - 0s
0 0 9.26260 0 222 9.67192 9.26260 4.23% - 0s
0 0 9.26421 0 221 9.67192 9.26421 4.22% - 0s
0 0 9.26545 0 236 9.67192 9.26545 4.20% - 0s
0 0 9.26581 0 240 9.67192 9.26581 4.20% - 0s
0 0 9.26616 0 234 9.67192 9.26616 4.20% - 0s
0 0 9.26619 0 236 9.67192 9.26619 4.19% - 0s
0 0 9.29544 0 244 9.67192 9.29544 3.89% - 0s
0 0 9.29767 0 257 9.67192 9.29767 3.87% - 0s
0 0 9.29809 0 253 9.67192 9.29809 3.87% - 0s
0 0 9.29813 0 257 9.67192 9.29813 3.86% - 0s
0 0 9.32088 0 257 9.67192 9.32088 3.63% - 0s
0 0 9.32334 0 261 9.67192 9.32334 3.60% - 0s
0 0 9.32589 0 275 9.67192 9.32589 3.58% - 0s
0 0 9.32647 0 277 9.67192 9.32647 3.57% - 0s
0 0 9.32654 0 275 9.67192 9.32654 3.57% - 1s
0 0 9.34360 0 259 9.67192 9.34360 3.39% - 1s
0 0 9.34560 0 275 9.67192 9.34560 3.37% - 1s
0 0 9.34587 0 269 9.67192 9.34587 3.37% - 1s
0 0 9.34589 0 279 9.67192 9.34589 3.37% - 1s
0 0 9.35925 0 255 9.67192 9.35925 3.23% - 1s
0 0 9.36095 0 279 9.67192 9.36095 3.22% - 1s
0 0 9.36129 0 282 9.67192 9.36129 3.21% - 1s
0 0 9.36145 0 280 9.67192 9.36145 3.21% - 1s
0 0 9.36785 0 280 9.67192 9.36785 3.14% - 1s
0 0 9.36918 0 296 9.67192 9.36918 3.13% - 1s
0 0 9.36961 0 296 9.67192 9.36961 3.13% - 1s
0 0 9.36987 0 306 9.67192 9.36987 3.12% - 1s
0 0 9.37368 0 284 9.67192 9.37368 3.08% - 2s
0 0 9.37408 0 296 9.67192 9.37408 3.08% - 2s
0 0 9.37460 0 301 9.67192 9.37460 3.07% - 2s
0 0 9.37467 0 303 9.67192 9.37467 3.07% - 2s
0 0 9.37680 0 302 9.67192 9.37680 3.05% - 2s
0 0 9.37732 0 302 9.67192 9.37732 3.05% - 2s
0 2 9.37760 0 302 9.67192 9.37760 3.04% - 2s
1122 1086 cutoff 22 9.67192 9.41872 2.62% 86.4 5s
1671 1406 9.67192 16 326 9.67192 9.44283 2.37% 83.3 10s
1700 1438 9.60404 17 274 9.67192 9.47806 2.00% 88.0 15s
4719 2763 9.73134 31 155 9.67192 9.58452 0.90% 102 20s
9996 6304 9.75133 33 130 9.67192 9.62710 0.46% 97.0 25s
16411 10268 9.75925 33 127 9.67192 9.65928 0.13% 92.1 30s
Optimal solution found at node 19451 - now completing solution pool...
Nodes | Current Node | Pool Obj. Bounds | Work
| | Worst |
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
19451 9613 9.73316 38 164 9.76768 9.67235 0.98% 91.6 32s
24063 8267 9.72004 39 134 9.75377 9.68169 0.74% 86.5 35s
Cutting planes:
Gomory: 23
Lift-and-project: 25
Cover: 53
Implied bound: 8
Projected implied bound: 4
Clique: 2
MIR: 314
StrongCG: 7
Flow cover: 246
Flow path: 2
GUB cover: 4
Inf proof: 7
Zero half: 72
Network: 9
RLT: 10
Relax-and-lift: 31
BQP: 1
Explored 25264 nodes (2153820 simplex iterations) in 35.07 seconds (32.58 work units)
Thread count was 16 (of 16 available processors)
Solution count 20: 9.67192 9.68346 9.69748 ... 9.75078
No other solutions better than 9.68462
Time limit reached
Best objective 9.671920168636e+00, best bound 9.671920168636e+00, gap 0.0000%
WARNING: Loading a SolverResults object with an 'aborted' status, but
containing a solution
[20]:
SolutionInfo(runtime=35.07800006866455, bound=9.671920168635916, objective=9.671920168635916, relgap=0.0, termination='maxTimeLimit')
[21]:
S, G = solver.get_solution()
[22]:
svgplot(G)
[22]:
[23]:
1 - G.size(weight='length')/G_ref.size(weight='length')
[23]:
0.024457285866890444
[24]:
with open('cazzaro_2022_comparison_κ_6_radial_balanced.dill', 'wb') as outfile:
dill.dump(G, outfile)