{ "cells": [ { "cell_type": "markdown", "id": "0e2b76a4-f1d7-4dd5-88c1-0d622df5bd49", "metadata": {}, "source": [ "# 3.6.2 Cazzaro and Pisinger 2022 Fig. 6" ] }, { "cell_type": "markdown", "id": "7da558c5-033b-4fa8-9841-4b7f7b75d138", "metadata": {}, "source": [ "This is used in the paper **Flexible cable routing framework for wind farm collection system optimization**." ] }, { "cell_type": "code", "execution_count": 1, "id": "2278cd98-3fcb-428b-842b-802f13af7c2e", "metadata": {}, "outputs": [], "source": [ "import dill\n", "from importlib.resources import files\n", "from matplotlib import pyplot as plt" ] }, { "cell_type": "code", "execution_count": 2, "id": "c69dd56e-dc8e-43cd-bcc5-b284c2a18300", "metadata": {}, "outputs": [], "source": [ "from optiwindnet.interarraylib import G_from_S\n", "from optiwindnet.svg import svgplot\n", "from optiwindnet.plotting import pplot\n", "from optiwindnet.mesh import make_planar_embedding\n", "from optiwindnet.baselines.hgs import hgs_multiroot\n", "from optiwindnet.importer import L_from_yaml\n", "from optiwindnet.pathfinding import PathFinder\n", "from optiwindnet.MILP import solver_factory, ModelOptions" ] }, { "cell_type": "code", "execution_count": 3, "id": "70241594-b980-4588-8e68-2981e1a4850a", "metadata": {}, "outputs": [], "source": [ "%config InlineBackend.figure_formats = ['svg']\n", "plt.rcParams['svg.fonttype'] = 'none'" ] }, { "cell_type": "markdown", "id": "fcf076a3-3b88-4805-8c4b-b542ce88a555", "metadata": {}, "source": [ "## Reference solution" ] }, { "cell_type": "markdown", "id": "1a7e6518-c670-45ca-a610-9b263c442bea", "metadata": {}, "source": [ "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" ] }, { "cell_type": "code", "execution_count": 4, "id": "e978d022-7efc-4a65-9d28-61879eee3134", "metadata": {}, "outputs": [], "source": [ "G_ref = dill.load(open('data/cazzaro_2022_paper_routeset.dill', 'rb'))" ] }, { "cell_type": "code", "execution_count": 5, "id": "4c5be888-9dae-4a34-9eda-8b3fe90aed23", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 9.9398 m(+0) α: 9κ = 6, T = 50" ], "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "svgplot(G_ref)" ] }, { "cell_type": "markdown", "id": "2386ab9b-0570-4206-8262-af30725d06a7", "metadata": {}, "source": [ "## Start here" ] }, { "cell_type": "code", "execution_count": 6, "id": "7fbfa19d-98e9-4183-9959-f71919aff71a", "metadata": {}, "outputs": [], "source": [ "solver = solver_factory('gurobi')" ] }, { "cell_type": "code", "execution_count": 7, "id": "c282d7c0-7f50-423f-9e4e-a69d13518d04", "metadata": {}, "outputs": [], "source": [ "L = L_from_yaml(files('optiwindnet.data') / 'Cazzaro-2022.yaml')" ] }, { "cell_type": "code", "execution_count": 8, "id": "bc633875-a777-42a1-8130-d6931eef88d1", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "" ], "text/plain": [ "" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "svgplot(L)" ] }, { "cell_type": "code", "execution_count": 9, "id": "91bf5be2-adb5-4bd9-9b5e-a06eb2b26157", "metadata": {}, "outputs": [], "source": [ "P, A = make_planar_embedding(L)" ] }, { "cell_type": "code", "execution_count": 10, "id": "ea6f4cc9-873a-456d-9fbf-67eaf9c1f896", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "" ], "text/plain": [ "" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "svgplot(A)" ] }, { "cell_type": "code", "execution_count": 11, "id": "b792422a-2397-410e-8d77-a68a8d57a36e", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", " \n", " 2025-06-23T13:23:50.372367\n", " image/svg+xml\n", " \n", " \n", " Matplotlib v3.10.3, https://matplotlib.org/\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "\n" ], "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "pplot(P, A);" ] }, { "cell_type": "markdown", "id": "f2850052-f689-41ee-9e0f-f48501d142b2", "metadata": {}, "source": [ "## Pre-solve" ] }, { "cell_type": "code", "execution_count": 12, "id": "fda5853e-02fc-49f0-8a3d-f949957829f8", "metadata": {}, "outputs": [], "source": [ "Sʹ = hgs_multiroot(A, capacity=6, time_limit=0.5, balanced=True)" ] }, { "cell_type": "code", "execution_count": 13, "id": "3019df2d-b306-4c8b-b0f0-7a2ce88505fa", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(0.04,)" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sʹ.graph['solution_time']" ] }, { "cell_type": "code", "execution_count": 14, "id": "e75028df-44ae-49c1-b636-f992ecfd5818", "metadata": {}, "outputs": [], "source": [ "Gʹ = G_from_S(Sʹ, A)" ] }, { "cell_type": "code", "execution_count": 15, "id": "fe1cc325-4702-4b3c-a297-97c6d620a621", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 9.6983 m(+0) α: 9κ = 6, T = 50" ], "text/plain": [ "" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "svgplot(Gʹ)" ] }, { "cell_type": "code", "execution_count": 16, "id": "43b99677-32e7-4181-a526-fa1db5b6c533", "metadata": {}, "outputs": [], "source": [ "Hʹ = PathFinder(Gʹ, planar=P, A=A).create_detours()" ] }, { "cell_type": "code", "execution_count": 17, "id": "31842fc3-e821-448c-aa2c-7e610d12e881", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 9.8049 m(+0) α: 9κ = 6, T = 50" ], "text/plain": [ "" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "svgplot(Hʹ)" ] }, { "cell_type": "code", "execution_count": 18, "id": "06df5315-38d3-4e26-afbb-fbcdab3b1b6a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.013578500078660682" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - Hʹ.size(weight='length')/G_ref.size(weight='length')" ] }, { "cell_type": "code", "execution_count": 21, "id": "5770c9ba-aba5-48f9-99fb-f6c25893dd1f", "metadata": {}, "outputs": [], "source": [ "solver.set_problem(\n", " P, A,\n", " capacity=6,\n", " model_options=ModelOptions(\n", " topology=\"radial\",\n", " feeder_route=\"segmented\",\n", " feeder_limit=\"minimum\",\n", " balanced=True,\n", " ),\n", " warmstart=Sʹ,\n", ")" ] }, { "cell_type": "code", "execution_count": 69, "id": "fc0c57c8-62bb-481f-8192-72b692e75789", "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter OutputFlag to value 1\n", "Gurobi Optimizer version 12.0.2 build v12.0.2rc0 (win64 - Windows 11.0 (26100.2))\n", "\n", "CPU model: 11th Gen Intel(R) Core(TM) i7-11850H @ 2.50GHz, instruction set [SSE2|AVX|AVX2|AVX512]\n", "Thread count: 8 physical cores, 16 logical processors, using up to 16 threads\n", "\n", "Non-default parameters:\n", "TimeLimit 35\n", "MIPGap 0.005\n", "MIPFocus 2\n", "PoolSolutions 20\n", "PoolSearchMode 2\n", "PoolGap 0.015\n", "\n", "Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk\n", "Optimize a model with 1443 rows, 872 columns and 5392 nonzeros\n", "Model fingerprint: 0xc18dc203\n", "Variable types: 0 continuous, 872 integer (436 binary)\n", "Coefficient statistics:\n", " Matrix range [1e+00, 6e+00]\n", " Objective range [6e-02, 1e+00]\n", " Bounds range [1e+00, 6e+00]\n", " RHS range [1e+00, 5e+01]\n", "\n", "Loaded user MIP start with objective 9.69831\n", "\n", "Presolve removed 193 rows and 0 columns\n", "Presolve time: 0.01s\n", "Presolved: 1250 rows, 872 columns, 4908 nonzeros\n", "Variable types: 0 continuous, 872 integer (436 binary)\n", "Root relaxation presolved: 1248 rows, 872 columns, 4876 nonzeros\n", "\n", "\n", "Root relaxation: objective 8.997354e+00, 885 iterations, 0.02 seconds (0.02 work units)\n", "\n", " Nodes | Current Node | Objective Bounds | Work\n", " Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time\n", "\n", " 0 0 8.99735 0 145 9.69831 8.99735 7.23% - 0s\n", " 0 0 9.20198 0 217 9.69831 9.20198 5.12% - 0s\n", " 0 0 9.28837 0 212 9.69831 9.28837 4.23% - 0s\n", " 0 0 9.29008 0 216 9.69831 9.29008 4.21% - 0s\n", " 0 0 9.29008 0 223 9.69831 9.29008 4.21% - 0s\n", " 0 0 9.29008 0 216 9.69831 9.29008 4.21% - 0s\n", " 0 0 9.32004 0 234 9.69831 9.32004 3.90% - 0s\n", " 0 0 9.32208 0 246 9.69831 9.32208 3.88% - 0s\n", " 0 0 9.32273 0 251 9.69831 9.32273 3.87% - 0s\n", " 0 0 9.32298 0 248 9.69831 9.32298 3.87% - 0s\n", " 0 0 9.32298 0 248 9.69831 9.32298 3.87% - 0s\n", " 0 0 9.33646 0 262 9.69831 9.33646 3.73% - 1s\n", " 0 0 9.34009 0 275 9.69831 9.34009 3.69% - 1s\n", " 0 0 9.34023 0 279 9.69831 9.34023 3.69% - 1s\n", " 0 0 9.35065 0 282 9.69831 9.35065 3.58% - 1s\n", " 0 0 9.35299 0 274 9.69831 9.35299 3.56% - 1s\n", " 0 0 9.35345 0 285 9.69831 9.35345 3.56% - 1s\n", " 0 0 9.35389 0 294 9.69831 9.35389 3.55% - 1s\n", " 0 0 9.35408 0 287 9.69831 9.35408 3.55% - 1s\n", " 0 0 9.36799 0 273 9.69831 9.36799 3.41% - 1s\n", " 0 0 9.37233 0 295 9.69831 9.37233 3.36% - 1s\n", " 0 0 9.37373 0 286 9.69831 9.37373 3.35% - 1s\n", " 0 0 9.37387 0 292 9.69831 9.37387 3.35% - 1s\n", " 0 0 9.38179 0 296 9.69831 9.38179 3.26% - 2s\n", " 0 0 9.38312 0 308 9.69831 9.38312 3.25% - 2s\n", " 0 0 9.38330 0 306 9.69831 9.38330 3.25% - 2s\n", " 0 0 9.39036 0 276 9.69831 9.39036 3.18% - 2s\n", " 0 0 9.39317 0 300 9.69831 9.39317 3.15% - 2s\n", " 0 0 9.39347 0 302 9.69831 9.39347 3.14% - 2s\n", " 0 0 9.39351 0 308 9.69831 9.39351 3.14% - 2s\n", " 0 0 9.40032 0 288 9.69831 9.40032 3.07% - 2s\n", " 0 0 9.40364 0 294 9.69831 9.40364 3.04% - 2s\n", " 0 0 9.40401 0 310 9.69831 9.40401 3.03% - 2s\n", " 0 0 9.40417 0 314 9.69831 9.40417 3.03% - 2s\n", " 0 0 9.41249 0 298 9.69831 9.41249 2.95% - 3s\n", " 0 0 9.41372 0 296 9.69831 9.41372 2.93% - 3s\n", " 0 0 9.41379 0 300 9.69831 9.41379 2.93% - 3s\n", " 0 0 9.41764 0 294 9.69831 9.41764 2.89% - 3s\n", " 0 0 9.41823 0 283 9.69831 9.41823 2.89% - 3s\n", " 0 0 9.41841 0 295 9.69831 9.41841 2.89% - 3s\n", " 0 0 9.42136 0 292 9.69831 9.42136 2.86% - 3s\n", " 0 0 9.42137 0 292 9.69831 9.42137 2.86% - 3s\n", " 0 2 9.42142 0 292 9.69831 9.42142 2.85% - 4s\n", " 356 362 9.81496 42 188 9.69831 9.43757 2.69% 122 5s\n", " 1676 1351 9.66313 23 297 9.69831 9.48726 2.18% 109 10s\n", " 2237 1674 9.69656 23 174 9.69831 9.53857 1.65% 115 15s\n", " 7482 4464 cutoff 27 9.69831 9.61913 0.82% 89.6 20s\n", " 13194 8350 infeasible 30 9.69831 9.65352 0.46% 85.8 25s\n", " 19186 12363 cutoff 36 9.69831 9.67969 0.19% 83.4 30s\n", "\n", "Optimal solution found at node 25155 - now completing solution pool...\n", "\n", " Nodes | Current Node | Pool Obj. Bounds | Work\n", " | | Worst |\n", " Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time\n", "\n", " 25155 12577 9.79601 22 232 9.80717 9.70040 1.09% 81.4 35s\n", "\n", "Cutting planes:\n", " Gomory: 19\n", " Lift-and-project: 19\n", " Cover: 60\n", " Implied bound: 11\n", " MIR: 280\n", " StrongCG: 14\n", " Flow cover: 272\n", " Flow path: 3\n", " GUB cover: 3\n", " Inf proof: 5\n", " Zero half: 67\n", " Network: 10\n", " RLT: 8\n", " Relax-and-lift: 29\n", " BQP: 4\n", "\n", "Explored 26394 nodes (2117513 simplex iterations) in 35.08 seconds (33.93 work units)\n", "Thread count was 16 (of 16 available processors)\n", "\n", "Solution count 20: 9.69831 9.70305 9.72387 ... 9.78342\n", "No other solutions better than 9.70222\n", "\n", "Time limit reached\n", "Best objective 9.698310786396e+00, best bound 9.698310786396e+00, gap 0.0000%\n", "WARNING: Loading a SolverResults object with an 'aborted' status, but\n", "containing a solution\n" ] }, { "data": { "text/plain": [ "SolutionInfo(runtime=35.08200001716614, bound=9.698310786396384, objective=9.698310786396384, relgap=0.0, termination='maxTimeLimit')" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solver.solve(\n", " mip_gap=0.005,\n", " time_limit=35,\n", " verbose=True,\n", " options=dict(\n", " mipfocus=2,\n", " poolgap=0.015,\n", " poolsearchmode=2,\n", " poolsolutions=20\n", " ),\n", ")" ] }, { "cell_type": "code", "execution_count": 70, "id": "3c75131a-5127-432d-8c54-2e1e0ae6fe31", "metadata": {}, "outputs": [], "source": [ "S, G = solver.get_solution()" ] }, { "cell_type": "code", "execution_count": 71, "id": "95c69a6b-1125-4018-bca3-ef0ba62bbce2", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 9.7654 m(+0) α: 9κ = 6, T = 50" ], "text/plain": [ "" ] }, "execution_count": 71, "metadata": {}, "output_type": "execute_result" } ], "source": [ "svgplot(G)" ] }, { "cell_type": "code", "execution_count": 72, "id": "e12d9cac-f140-4d1c-91df-e97608e8f4ae", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.017546306686529123" ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - G.size(weight='length')/G_ref.size(weight='length')" ] }, { "cell_type": "code", "execution_count": 73, "id": "58bf3009-3ebd-4730-a3a2-696ed3e5aaf4", "metadata": {}, "outputs": [], "source": [ "with open('cazzaro_2022_comparison_κ_6_radial_balanced.dill', 'wb') as outfile:\n", " dill.dump(G, outfile)" ] } ], "metadata": { "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 5 }