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, svgpplot
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]:
svgpplot(P, A)
[11]:
Pre-solve¶
[12]:
Sʹ = hgs_cvrp(A, capacity=6, time_limit=0.5, balanced=True)
Sʹ.graph['solution_time']
[12]:
0.47
[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ʹ,
)
Set parameter WLSAccessID
Set parameter WLSSecret
Set parameter LicenseID to value 937681
Set parameter MIPFocus to value 1
Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk
[17]:
solver.solve(
mip_gap=0.005,
time_limit=35,
verbose=True,
options=dict(
mipfocus=2,
poolgap=0.015,
poolsearchmode=2,
poolsolutions=20
),
)
Set parameter MIPFocus to value 2
Set parameter PoolGap to value 0.015
Set parameter PoolSearchMode to value 2
Set parameter PoolSolutions to value 20
Set parameter TimeLimit to value 35
Set parameter MIPGap to value 0.005
Gurobi Optimizer version 13.0.2 build v13.0.2rc1 (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: 0x1b77179f
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.948966e+00, 1052 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.94897 0 123 9.67192 8.94897 7.47% - 0s
0 0 9.23090 0 194 9.67192 9.23090 4.56% - 0s
0 0 9.30911 0 205 9.67192 9.30911 3.75% - 0s
0 0 9.30911 0 215 9.67192 9.30911 3.75% - 0s
0 0 9.30911 0 215 9.67192 9.30911 3.75% - 0s
0 0 9.34235 0 237 9.67192 9.34235 3.41% - 0s
0 0 9.34235 0 238 9.67192 9.34235 3.41% - 0s
0 0 9.34235 0 232 9.67192 9.34235 3.41% - 0s
0 0 9.34975 0 230 9.67192 9.34975 3.33% - 0s
0 0 9.40534 0 259 9.67192 9.40534 2.76% - 0s
0 0 9.40629 0 257 9.67192 9.40629 2.75% - 0s
0 0 9.40629 0 259 9.67192 9.40629 2.75% - 0s
0 0 9.40677 0 261 9.67192 9.40677 2.74% - 0s
0 0 9.40805 0 225 9.67192 9.40805 2.73% - 0s
0 0 9.40829 0 252 9.67192 9.40829 2.73% - 0s
0 0 9.40833 0 242 9.67192 9.40833 2.73% - 0s
0 0 9.40833 0 245 9.67192 9.40833 2.73% - 0s
0 0 9.41188 0 252 9.67192 9.41188 2.69% - 1s
0 0 9.41232 0 266 9.67192 9.41232 2.68% - 1s
0 0 9.41232 0 274 9.67192 9.41232 2.68% - 1s
0 0 9.41232 0 274 9.67192 9.41232 2.68% - 1s
0 0 9.42500 0 258 9.67192 9.42500 2.55% - 1s
0 0 9.42500 0 266 9.67192 9.42500 2.55% - 1s
0 0 9.42500 0 259 9.67192 9.42500 2.55% - 1s
0 0 9.42516 0 268 9.67192 9.42516 2.55% - 1s
0 0 9.43718 0 275 9.67192 9.43718 2.43% - 1s
0 0 9.43872 0 271 9.67192 9.43872 2.41% - 1s
0 0 9.43872 0 274 9.67192 9.43872 2.41% - 1s
0 0 9.44535 0 249 9.67192 9.44535 2.34% - 1s
0 0 9.44535 0 252 9.67192 9.44535 2.34% - 1s
0 0 9.44535 0 249 9.67192 9.44535 2.34% - 1s
0 0 9.44730 0 265 9.67192 9.44730 2.32% - 1s
0 0 9.44730 0 278 9.67192 9.44730 2.32% - 1s
0 0 9.44977 0 276 9.67192 9.44977 2.30% - 2s
0 0 9.44977 0 276 9.67192 9.44977 2.30% - 2s
0 0 9.44977 0 276 9.67192 9.44977 2.30% - 2s
0 2 9.44977 0 276 9.67192 9.44977 2.30% - 2s
1614 1024 9.56562 14 276 9.67192 9.49893 1.79% 66.5 5s
1818 1168 9.61927 21 238 9.67192 9.51213 1.65% 73.6 10s
7772 4656 infeasible 30 9.67192 9.60852 0.66% 89.0 15s
14810 9113 9.75092 24 222 9.67192 9.65409 0.18% 93.4 20s
Optimal solution found at node 18667 - now completing solution pool...
Nodes | Current Node | Pool Obj. Bounds | Work
| | Worst |
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
18667 9980 9.77549 29 206 9.79597 9.67198 1.27% 92.5 22s
24630 5530 9.70718 29 137 9.74255 9.68556 0.59% 85.8 25s
Cutting planes:
Gomory: 24
Lift-and-project: 11
Cover: 41
Implied bound: 14
Projected implied bound: 1
Clique: 3
MIR: 218
StrongCG: 5
Flow cover: 223
Flow path: 3
GUB cover: 2
Inf proof: 3
Zero half: 82
Network: 28
RLT: 7
Relax-and-lift: 20
BQP: 4
Explored 25555 nodes (2173334 simplex iterations) in 25.23 seconds (29.77 work units)
Thread count was 16 (of 16 available processors)
Solution count 20: 9.67192 9.68346 9.69748 ... 9.73763
No other solutions better than 9.73763
Optimal solution found (tolerance 5.00e-03)
Best objective 9.671920168636e+00, best bound 9.671920168636e+00, gap 0.0000%
[17]:
SolutionInfo(runtime=25.23669409751892, 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)