{ "cells": [ { "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-07-31T08:05:19.086735\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.18,)" ] }, "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.6719 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": 19, "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": 20, "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: 0xe1034d1b\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.67192\n", "\n", "Presolve removed 193 rows and 0 columns\n", "Presolve time: 0.02s\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.956774e+00, 977 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.95677 0 127 9.67192 8.95677 7.39% - 0s\n", " 0 0 9.18053 0 168 9.67192 9.18053 5.08% - 0s\n", " 0 0 9.18100 0 168 9.67192 9.18100 5.08% - 0s\n", " 0 0 9.26260 0 222 9.67192 9.26260 4.23% - 0s\n", " 0 0 9.26421 0 221 9.67192 9.26421 4.22% - 0s\n", " 0 0 9.26545 0 236 9.67192 9.26545 4.20% - 0s\n", " 0 0 9.26581 0 240 9.67192 9.26581 4.20% - 0s\n", " 0 0 9.26616 0 234 9.67192 9.26616 4.20% - 0s\n", " 0 0 9.26619 0 236 9.67192 9.26619 4.19% - 0s\n", " 0 0 9.29544 0 244 9.67192 9.29544 3.89% - 0s\n", " 0 0 9.29767 0 257 9.67192 9.29767 3.87% - 0s\n", " 0 0 9.29809 0 253 9.67192 9.29809 3.87% - 0s\n", " 0 0 9.29813 0 257 9.67192 9.29813 3.86% - 0s\n", " 0 0 9.32088 0 257 9.67192 9.32088 3.63% - 0s\n", " 0 0 9.32334 0 261 9.67192 9.32334 3.60% - 0s\n", " 0 0 9.32589 0 275 9.67192 9.32589 3.58% - 0s\n", " 0 0 9.32647 0 277 9.67192 9.32647 3.57% - 0s\n", " 0 0 9.32654 0 275 9.67192 9.32654 3.57% - 1s\n", " 0 0 9.34360 0 259 9.67192 9.34360 3.39% - 1s\n", " 0 0 9.34560 0 275 9.67192 9.34560 3.37% - 1s\n", " 0 0 9.34587 0 269 9.67192 9.34587 3.37% - 1s\n", " 0 0 9.34589 0 279 9.67192 9.34589 3.37% - 1s\n", " 0 0 9.35925 0 255 9.67192 9.35925 3.23% - 1s\n", " 0 0 9.36095 0 279 9.67192 9.36095 3.22% - 1s\n", " 0 0 9.36129 0 282 9.67192 9.36129 3.21% - 1s\n", " 0 0 9.36145 0 280 9.67192 9.36145 3.21% - 1s\n", " 0 0 9.36785 0 280 9.67192 9.36785 3.14% - 1s\n", " 0 0 9.36918 0 296 9.67192 9.36918 3.13% - 1s\n", " 0 0 9.36961 0 296 9.67192 9.36961 3.13% - 1s\n", " 0 0 9.36987 0 306 9.67192 9.36987 3.12% - 1s\n", " 0 0 9.37368 0 284 9.67192 9.37368 3.08% - 2s\n", " 0 0 9.37408 0 296 9.67192 9.37408 3.08% - 2s\n", " 0 0 9.37460 0 301 9.67192 9.37460 3.07% - 2s\n", " 0 0 9.37467 0 303 9.67192 9.37467 3.07% - 2s\n", " 0 0 9.37680 0 302 9.67192 9.37680 3.05% - 2s\n", " 0 0 9.37732 0 302 9.67192 9.37732 3.05% - 2s\n", " 0 2 9.37760 0 302 9.67192 9.37760 3.04% - 2s\n", " 1122 1086 cutoff 22 9.67192 9.41872 2.62% 86.4 5s\n", " 1671 1406 9.67192 16 326 9.67192 9.44283 2.37% 83.3 10s\n", " 1700 1438 9.60404 17 274 9.67192 9.47806 2.00% 88.0 15s\n", " 4719 2763 9.73134 31 155 9.67192 9.58452 0.90% 102 20s\n", " 9996 6304 9.75133 33 130 9.67192 9.62710 0.46% 97.0 25s\n", " 16411 10268 9.75925 33 127 9.67192 9.65928 0.13% 92.1 30s\n", "\n", "Optimal solution found at node 19451 - 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", " 19451 9613 9.73316 38 164 9.76768 9.67235 0.98% 91.6 32s\n", " 24063 8267 9.72004 39 134 9.75377 9.68169 0.74% 86.5 35s\n", "\n", "Cutting planes:\n", " Gomory: 23\n", " Lift-and-project: 25\n", " Cover: 53\n", " Implied bound: 8\n", " Projected implied bound: 4\n", " Clique: 2\n", " MIR: 314\n", " StrongCG: 7\n", " Flow cover: 246\n", " Flow path: 2\n", " GUB cover: 4\n", " Inf proof: 7\n", " Zero half: 72\n", " Network: 9\n", " RLT: 10\n", " Relax-and-lift: 31\n", " BQP: 1\n", "\n", "Explored 25264 nodes (2153820 simplex iterations) in 35.07 seconds (32.58 work units)\n", "Thread count was 16 (of 16 available processors)\n", "\n", "Solution count 20: 9.67192 9.68346 9.69748 ... 9.75078\n", "No other solutions better than 9.68462\n", "\n", "Time limit reached\n", "Best objective 9.671920168636e+00, best bound 9.671920168636e+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.07800006866455, bound=9.671920168635916, objective=9.671920168635916, relgap=0.0, termination='maxTimeLimit')" ] }, "execution_count": 20, "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": 21, "id": "3c75131a-5127-432d-8c54-2e1e0ae6fe31", "metadata": {}, "outputs": [], "source": [ "S, G = solver.get_solution()" ] }, { "cell_type": "code", "execution_count": 22, "id": "95c69a6b-1125-4018-bca3-ef0ba62bbce2", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 9.6967 m(+0) α: 9κ = 6, T = 50" ], "text/plain": [ "" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "svgplot(G)" ] }, { "cell_type": "code", "execution_count": 23, "id": "e12d9cac-f140-4d1c-91df-e97608e8f4ae", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.024457285866890444" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - G.size(weight='length')/G_ref.size(weight='length')" ] }, { "cell_type": "code", "execution_count": 24, "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 }