{ "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 pickle\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_cvrp\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 = pickle.load(open('data/cazzaro_2022_paper_routeset.pkl', 'rb'))" ] }, { "cell_type": "code", "execution_count": 5, "id": "4c5be888-9dae-4a34-9eda-8b3fe90aed23", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 9.9398 m(+0) [-1]: 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", " 2026-03-06T15:04:17.940054\n", " image/svg+xml\n", " \n", " \n", " Matplotlib v3.10.8, 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": "5a063194-a673-4788-9a2a-9a6fa1f70471", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(0.18,)" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sʹ = hgs_cvrp(A, capacity=6, time_limit=0.5, balanced=True)\n", "Sʹ.graph['solution_time']" ] }, { "cell_type": "code", "execution_count": 13, "id": "2420dff2-7dbc-4e75-b412-d2d33a0d86e8", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 9.6719 m(+0) [-1]: 9κ = 6, T = 50" ], "text/plain": [ "" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Gʹ = G_from_S(Sʹ, A)\n", "svgplot(Gʹ)" ] }, { "cell_type": "code", "execution_count": 14, "id": "fe415c00-e060-4bb4-ba61-1496112791ae", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 9.8049 m(+0) [-1]: 9κ = 6, T = 50" ], "text/plain": [ "" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Hʹ = PathFinder(Gʹ, planar=P, A=A).create_detours()\n", "svgplot(Hʹ)" ] }, { "cell_type": "code", "execution_count": 15, "id": "06df5315-38d3-4e26-afbb-fbcdab3b1b6a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.013578500078660682" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - Hʹ.size(weight='length')/G_ref.size(weight='length')" ] }, { "cell_type": "code", "execution_count": 16, "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": 17, "id": "fc0c57c8-62bb-481f-8192-72b692e75789", "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Gurobi Optimizer version 13.0.1 build v13.0.1rc0 (linux64 - \"Debian GNU/Linux forky/sid\")\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 1442 rows, 872 columns and 5342 nonzeros (Min)\n", "Model fingerprint: 0x43b98d1c\n", "Model has 436 linear objective coefficients\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 192 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.956774e+00, 983 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.22792 0 187 9.67192 9.22792 4.59% - 0s\n", " 0 0 9.29995 0 204 9.67192 9.29995 3.85% - 0s\n", " 0 0 9.29995 0 215 9.67192 9.29995 3.85% - 0s\n", " 0 0 9.30038 0 212 9.67192 9.30038 3.84% - 0s\n", " 0 0 9.30049 0 223 9.67192 9.30049 3.84% - 0s\n", " 0 0 9.33383 0 248 9.67192 9.33383 3.50% - 0s\n", " 0 0 9.33564 0 253 9.67192 9.33564 3.48% - 0s\n", " 0 0 9.33577 0 257 9.67192 9.33577 3.48% - 0s\n", " 0 0 9.37648 0 260 9.67192 9.37648 3.05% - 0s\n", " 0 0 9.37648 0 264 9.67192 9.37648 3.05% - 0s\n", " 0 0 9.37648 0 268 9.67192 9.37648 3.05% - 0s\n", " 0 0 9.38106 0 276 9.67192 9.38106 3.01% - 0s\n", " 0 0 9.39460 0 267 9.67192 9.39460 2.87% - 0s\n", " 0 0 9.39772 0 261 9.67192 9.39772 2.84% - 0s\n", " 0 0 9.39817 0 264 9.67192 9.39817 2.83% - 0s\n", " 0 0 9.39825 0 262 9.67192 9.39825 2.83% - 0s\n", " 0 0 9.40620 0 256 9.67192 9.40620 2.75% - 1s\n", " 0 0 9.40722 0 280 9.67192 9.40722 2.74% - 1s\n", " 0 0 9.40741 0 276 9.67192 9.40741 2.73% - 1s\n", " 0 0 9.42158 0 282 9.67192 9.42158 2.59% - 1s\n", " 0 0 9.42158 0 266 9.67192 9.42158 2.59% - 1s\n", " 0 0 9.42158 0 274 9.67192 9.42158 2.59% - 1s\n", " 0 0 9.42932 0 243 9.67192 9.42932 2.51% - 1s\n", " 0 0 9.43204 0 250 9.67192 9.43204 2.48% - 1s\n", " 0 0 9.43222 0 252 9.67192 9.43222 2.48% - 1s\n", " 0 0 9.43557 0 258 9.67192 9.43557 2.44% - 1s\n", " 0 0 9.43647 0 258 9.67192 9.43647 2.43% - 1s\n", " 0 0 9.43656 0 254 9.67192 9.43656 2.43% - 1s\n", " 0 0 9.43947 0 270 9.67192 9.43947 2.40% - 1s\n", " 0 0 9.44075 0 274 9.67192 9.44075 2.39% - 2s\n", " 0 0 9.44088 0 274 9.67192 9.44088 2.39% - 2s\n", " 0 0 9.44581 0 261 9.67192 9.44581 2.34% - 2s\n", " 0 0 9.44591 0 275 9.67192 9.44591 2.34% - 2s\n", " 0 0 9.44855 0 260 9.67192 9.44855 2.31% - 2s\n", " 0 0 9.44869 0 260 9.67192 9.44869 2.31% - 2s\n", " 0 0 9.44869 0 260 9.67192 9.44869 2.31% - 2s\n", " 0 2 9.44869 0 260 9.67192 9.44869 2.31% - 2s\n", " 1576 1323 9.67192 19 260 9.67192 9.51769 1.59% 96.3 5s\n", " 2409 1701 9.72112 27 162 9.67192 9.54386 1.32% 98.8 10s\n", " 9832 6289 9.72235 48 202 9.67192 9.62786 0.46% 85.9 15s\n", "\n", "Optimal solution found at node 18498 - 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", " 18498 11126 cutoff 30 9.80722 9.67305 1.37% 82.9 19s\n", " 20712 10704 9.74505 51 102 9.79341 9.67622 1.20% 80.0 20s\n", "\n", "Cutting planes:\n", " Gomory: 24\n", " Lift-and-project: 8\n", " Cover: 53\n", " Implied bound: 10\n", " Projected implied bound: 3\n", " Clique: 3\n", " MIR: 203\n", " StrongCG: 5\n", " Flow cover: 219\n", " Flow path: 5\n", " Inf proof: 2\n", " Zero half: 89\n", " Network: 22\n", " RLT: 7\n", " Relax-and-lift: 20\n", "\n", "Explored 30072 nodes (2168766 simplex iterations) in 22.91 seconds (26.36 work units)\n", "Thread count was 16 (of 16 available processors)\n", "\n", "Solution count 20: 9.67192 9.68346 9.69748 ... 9.73464\n", "No other solutions better than 9.73464\n", "\n", "Optimal solution found (tolerance 5.00e-03)\n", "Best objective 9.671920168636e+00, best bound 9.671920168636e+00, gap 0.0000%\n" ] }, { "data": { "text/plain": [ "SolutionInfo(runtime=22.922324180603027, bound=9.671920168635916, objective=9.671920168635916, relgap=0.0, termination='optimal')" ] }, "execution_count": 17, "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": 18, "id": "0d3fb568-f260-420e-98d4-5e9761edb63e", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 9.6967 m(+0) [-1]: 9κ = 6, T = 50" ], "text/plain": [ "" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S, G = solver.get_solution()\n", "svgplot(G)" ] }, { "cell_type": "code", "execution_count": 19, "id": "e12d9cac-f140-4d1c-91df-e97608e8f4ae", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.024457285866890444" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - G.size(weight='length')/G_ref.size(weight='length')" ] }, { "cell_type": "code", "execution_count": 20, "id": "58bf3009-3ebd-4730-a3a2-696ed3e5aaf4", "metadata": {}, "outputs": [], "source": [ "with open('cazzaro_2022_comparison_κ_6_radial_balanced.pkl', 'wb') as outfile:\n", " pickle.dump(G, outfile)" ] } ], "metadata": { "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 5 }