{ "cells": [ { "cell_type": "code", "execution_count": 1, "id": "a6014338-3264-458f-aa42-abf810aac247", "metadata": {}, "outputs": [], "source": [ "import dill" ] }, { "cell_type": "code", "execution_count": 2, "id": "cdd0f9ce-4a20-4b4f-a67d-3d757ce40e2d", "metadata": {}, "outputs": [], "source": [ "from importlib.resources import files" ] }, { "cell_type": "code", "execution_count": 3, "id": "452b3d4e-30a8-4d45-ad9b-130e4b1b1b82", "metadata": {}, "outputs": [], "source": [ "from optiwindnet.interarraylib import G_from_S\n", "from optiwindnet.svg import svgplot\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\n", "from optiwindnet.interarraylib import as_normalized" ] }, { "cell_type": "markdown", "id": "bc11f1a4-3ffd-4459-9cec-2cb933b0ad10", "metadata": {}, "source": [ "## Reference solution" ] }, { "cell_type": "markdown", "id": "61f8051d-e682-4287-b550-620223283ab1", "metadata": {}, "source": [ "Yi, X., Scutariu, M., & Smith, K. (2019). Optimisation of offshore wind farm inter-array collection system. IET Renewable Power Generation, 13(11), 1990–1999. https://doi.org/10.1049/iet-rpg.2018.5805" ] }, { "cell_type": "markdown", "id": "3a7c8c80-1eea-4dc7-8449-4068953bd72c", "metadata": {}, "source": [ "The network was not parsed from the paper, using the published total cable lengths:\n", "- radial: 162.3 km\n", "- branched: 154.6 km" ] }, { "cell_type": "code", "execution_count": 4, "id": "25bf0211-9f18-4182-b5ec-d5f743cf1ff9", "metadata": {}, "outputs": [], "source": [ "λ_radial = 162300\n", "λ_branched = 154600" ] }, { "cell_type": "markdown", "id": "6164b356-5dbe-4029-a320-8a929293fcc2", "metadata": {}, "source": [ "## Start here" ] }, { "cell_type": "code", "execution_count": 5, "id": "b955e7cd-8523-424d-8b47-d00a947bbb3d", "metadata": {}, "outputs": [], "source": [ "solver = solver_factory('gurobi')" ] }, { "cell_type": "code", "execution_count": 6, "id": "923b258d-a5ea-4bfc-9f3f-a16bb08f6fcf", "metadata": {}, "outputs": [], "source": [ "base_dir = files('optiwindnet.data')\n", "inputfile = base_dir / 'Yi-2019.yaml'\n", "L = L_from_yaml(inputfile)" ] }, { "cell_type": "code", "execution_count": 7, "id": "53f516b4-c8a3-4eba-bbb4-a83a8193b43a", "metadata": { "scrolled": true }, "outputs": [], "source": [ "P, A = make_planar_embedding(L)\n", "A_norm = as_normalized(A)" ] }, { "cell_type": "code", "execution_count": 8, "id": "af9273d4-abf9-45e8-a911-3b4447e9de2a", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "" ], "text/plain": [ "" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "svgplot(A)" ] }, { "cell_type": "markdown", "id": "4d3530b1-331c-43c5-a978-acd5d6e7c299", "metadata": {}, "source": [ "## Solve κ = 6 (branched)" ] }, { "cell_type": "code", "execution_count": 9, "id": "77ea60a7-fad0-4995-93c3-a221c5414a25", "metadata": {}, "outputs": [], "source": [ "Sʹ = hgs_multiroot(A_norm, capacity=6, time_limit=0.5)" ] }, { "cell_type": "code", "execution_count": 10, "id": "455a3aea-7ef1-4240-ba55-3be63dac24ed", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(0.24, 0.2)" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sʹ.graph['solution_time']" ] }, { "cell_type": "code", "execution_count": 11, "id": "99379fef-c3ac-4f8b-9ee0-a22bb93eee45", "metadata": {}, "outputs": [], "source": [ "Gʹ = G_from_S(Sʹ, A)" ] }, { "cell_type": "code", "execution_count": 12, "id": "c594d494-ad0d-4960-af4d-ec8267383d3e", "metadata": {}, "outputs": [], "source": [ "Hʹ = PathFinder(Gʹ, planar=P, A=A).create_detours()" ] }, { "cell_type": "code", "execution_count": 13, "id": "d02478f1-8058-420d-93c7-16080ef89191", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 136877.0 m(+0) α: 9, β: 11κ = 6, T = 119" ], "text/plain": [ "" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "svgplot(Hʹ)" ] }, { "cell_type": "code", "execution_count": 14, "id": "3f23c99d-6818-45cb-b333-293177ceca3c", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.11463530574482794" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - Hʹ.size(weight='length')/λ_branched" ] }, { "cell_type": "code", "execution_count": 15, "id": "6e902710-5a21-4a81-8bae-c7eea9da1489", "metadata": {}, "outputs": [], "source": [ "solver.set_problem(\n", " P, A_norm,\n", " capacity=Sʹ.graph['capacity'],\n", " model_options=ModelOptions(\n", " topology=\"branched\",\n", " feeder_route=\"segmented\",\n", " feeder_limit=\"minimum\",\n", " ),\n", " warmstart=Sʹ,\n", ")" ] }, { "cell_type": "code", "execution_count": 16, "id": "85fbb9b3-0b62-474d-b05e-1bdb2d630670", "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 45\n", "MIPGap 0.005\n", "MIPFocus 1\n", "\n", "Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk\n", "Optimize a model with 3852 rows, 2592 columns and 14542 nonzeros\n", "Model fingerprint: 0x73289d33\n", "Variable types: 0 continuous, 2592 integer (1296 binary)\n", "Coefficient statistics:\n", " Matrix range [1e+00, 6e+00]\n", " Objective range [5e-02, 1e+00]\n", " Bounds range [1e+00, 6e+00]\n", " RHS range [1e+00, 1e+02]\n", "\n", "Loaded user MIP start with objective 10.7844\n", "\n", "Presolve removed 414 rows and 0 columns\n", "Presolve time: 0.02s\n", "Presolved: 3438 rows, 2592 columns, 13240 nonzeros\n", "Variable types: 0 continuous, 2592 integer (1296 binary)\n", "\n", "Root relaxation: objective 9.966300e+00, 2570 iterations, 0.05 seconds (0.06 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 9.96630 0 177 10.78438 9.96630 7.59% - 0s\n", "H 0 0 10.7811045 9.96630 7.56% - 0s\n", "H 0 0 10.7810924 9.96630 7.56% - 0s\n", " 0 0 10.19621 0 203 10.78109 10.19621 5.43% - 0s\n", " 0 0 10.20900 0 227 10.78109 10.20900 5.31% - 0s\n", "H 0 0 10.7801061 10.20900 5.30% - 0s\n", " 0 0 10.24309 0 340 10.78011 10.24309 4.98% - 0s\n", " 0 0 10.25246 0 340 10.78011 10.25246 4.89% - 0s\n", "H 0 0 10.7768595 10.25246 4.87% - 0s\n", "H 0 0 10.7752908 10.25246 4.85% - 0s\n", " 0 0 10.27779 0 333 10.77529 10.27779 4.62% - 0s\n", "H 0 0 10.7553023 10.27779 4.44% - 0s\n", " 0 0 10.28714 0 390 10.75530 10.28714 4.35% - 0s\n", " 0 0 10.31266 0 402 10.75530 10.31266 4.12% - 1s\n", " 0 0 10.32084 0 399 10.75530 10.32084 4.04% - 1s\n", " 0 0 10.32617 0 394 10.75530 10.32617 3.99% - 1s\n", "H 0 0 10.7065847 10.32617 3.55% - 1s\n", " 0 2 10.32618 0 394 10.70658 10.32618 3.55% - 3s\n", "H 56 65 10.7000010 10.33991 3.37% 71.9 3s\n", "H 125 129 10.6754713 10.33991 3.14% 76.9 3s\n", "H 150 166 10.6439278 10.33991 2.86% 76.8 4s\n", " 316 322 10.41571 29 322 10.64393 10.33991 2.86% 69.2 5s\n", "H 1209 934 10.6075080 10.34766 2.45% 67.3 7s\n", "H 1693 1304 10.6069388 10.34766 2.44% 62.7 8s\n", " 1704 1312 10.38427 22 325 10.60694 10.35130 2.41% 62.3 10s\n", " 1721 1323 10.44380 29 473 10.60694 10.37906 2.15% 61.7 15s\n", "H 1872 1373 10.5883958 10.38233 1.95% 76.3 16s\n", "H 1911 1329 10.5881854 10.38233 1.94% 77.1 17s\n", " 2658 1572 10.40815 29 294 10.58819 10.38840 1.89% 78.7 20s\n", " 4951 2397 10.46417 30 214 10.58819 10.39554 1.82% 77.0 25s\n", " 8161 4555 10.51005 44 300 10.58819 10.39933 1.78% 73.7 30s\n", " 10194 6240 10.49454 45 192 10.58819 10.40518 1.73% 73.3 35s\n", " 13383 8359 10.50696 36 263 10.58819 10.40785 1.70% 74.0 40s\n", " 16578 10641 10.49905 32 316 10.58819 10.41065 1.68% 73.3 45s\n", "\n", "Cutting planes:\n", " Gomory: 30\n", " Lift-and-project: 8\n", " Cover: 9\n", " MIR: 273\n", " StrongCG: 15\n", " Flow cover: 258\n", " Flow path: 24\n", " GUB cover: 3\n", " Inf proof: 4\n", " Zero half: 8\n", " Mod-K: 8\n", " Network: 24\n", " RLT: 2\n", " Relax-and-lift: 24\n", "\n", "Explored 17019 nodes (1248869 simplex iterations) in 45.10 seconds (38.49 work units)\n", "Thread count was 16 (of 16 available processors)\n", "\n", "Solution count 10: 10.5882 10.5884 10.6069 ... 10.7753\n", "\n", "Time limit reached\n", "Best objective 1.058818539829e+01, best bound 1.041067879649e+01, gap 1.6765%\n", "WARNING: Loading a SolverResults object with an 'aborted' status, but\n", "containing a solution\n" ] }, { "data": { "text/plain": [ "SolutionInfo(runtime=45.104000091552734, bound=10.410678796494933, objective=10.588185398286745, relgap=0.016764591392641637, termination='maxTimeLimit')" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solver.solve(\n", " mip_gap=0.005,\n", " time_limit=45,\n", " verbose=True,\n", ")" ] }, { "cell_type": "code", "execution_count": 17, "id": "9125861e-66f6-4f58-8493-15cdf87ff607", "metadata": {}, "outputs": [], "source": [ "S, G = solver.get_solution(A)" ] }, { "cell_type": "code", "execution_count": 18, "id": "bd1a7c9a-1345-4de5-ad34-15168a5ef94d", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 133915.0 m(+0) α: 10, β: 10κ = 6, T = 119" ], "text/plain": [ "" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "svgplot(G)" ] }, { "cell_type": "code", "execution_count": 19, "id": "2b1b17e1-c564-40ee-a011-86ee7a3fd3a3", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.13379531445617387" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - G.size(weight='length')/λ_branched" ] }, { "cell_type": "code", "execution_count": 20, "id": "c9ac92f6-8f87-49b5-a74b-d3576a301d4d", "metadata": {}, "outputs": [], "source": [ "with open('yi_2019_κ_6_branched_our.dill', 'wb') as outfile:\n", " dill.dump(G, outfile)" ] }, { "cell_type": "markdown", "id": "1313de7c-2c1f-4cf9-9a11-12e6eee34827", "metadata": {}, "source": [ "## Solve κ = 6 (radial)" ] }, { "cell_type": "code", "execution_count": 21, "id": "47239a39-5aba-4287-bcb4-92c390c4a7a2", "metadata": {}, "outputs": [], "source": [ "Sʹ = hgs_multiroot(A_norm, capacity=6, time_limit=0.5)" ] }, { "cell_type": "code", "execution_count": 22, "id": "59a7b4f5-f994-4bd9-ba85-92a61bab8152", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(0.24, 0.22)" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sʹ.graph['solution_time']" ] }, { "cell_type": "code", "execution_count": 23, "id": "69179850-12ed-4791-96f3-58854857e2ee", "metadata": {}, "outputs": [], "source": [ "Gʹ = G_from_S(Sʹ, A)" ] }, { "cell_type": "code", "execution_count": 24, "id": "6d08640a-dd43-4ea3-b56f-dc5d8c8942b1", "metadata": {}, "outputs": [], "source": [ "Hʹ = PathFinder(Gʹ, planar=P, A=A).create_detours()" ] }, { "cell_type": "code", "execution_count": 25, "id": "e821c0e4-c5d1-4cb4-808d-ed64728b8aeb", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 136877.0 m(+0) α: 9, β: 11κ = 6, T = 119" ], "text/plain": [ "" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "svgplot(Hʹ)" ] }, { "cell_type": "code", "execution_count": 26, "id": "5faee4a5-6dab-4d01-8b79-dae262635db1", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.15663966893499937" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - Hʹ.size(weight='length')/λ_radial" ] }, { "cell_type": "code", "execution_count": 27, "id": "dcdc23dc-1a0e-4c2d-8934-73cbc5e5fe2f", "metadata": {}, "outputs": [], "source": [ "solver.set_problem(\n", " P, A_norm,\n", " capacity=Sʹ.graph['capacity'],\n", " model_options=ModelOptions(\n", " topology=\"radial\",\n", " feeder_route=\"segmented\",\n", " feeder_limit=\"minimum\",\n", " ),\n", " warmstart=Sʹ,\n", ")" ] }, { "cell_type": "code", "execution_count": 28, "id": "6fc6959d-4394-4212-a62e-6e07ce4f9cfc", "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 45\n", "MIPGap 0.005\n", "MIPFocus 1\n", "\n", "Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk\n", "Optimize a model with 3971 rows, 2592 columns and 15600 nonzeros\n", "Model fingerprint: 0xdfb2120a\n", "Variable types: 0 continuous, 2592 integer (1296 binary)\n", "Coefficient statistics:\n", " Matrix range [1e+00, 6e+00]\n", " Objective range [5e-02, 1e+00]\n", " Bounds range [1e+00, 6e+00]\n", " RHS range [1e+00, 1e+02]\n", "\n", "Loaded user MIP start with objective 10.7844\n", "\n", "Presolve removed 414 rows and 0 columns\n", "Presolve time: 0.03s\n", "Presolved: 3557 rows, 2592 columns, 14298 nonzeros\n", "Variable types: 0 continuous, 2592 integer (1296 binary)\n", "\n", "Root relaxation: objective 9.993809e+00, 2711 iterations, 0.06 seconds (0.07 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 9.99381 0 272 10.78438 9.99381 7.33% - 0s\n", " 0 0 10.23528 0 264 10.78438 10.23528 5.09% - 0s\n", " 0 0 10.24537 0 222 10.78438 10.24537 5.00% - 0s\n", " 0 0 10.29685 0 396 10.78438 10.29685 4.52% - 0s\n", " 0 0 10.29831 0 437 10.78438 10.29831 4.51% - 0s\n", " 0 0 10.32524 0 426 10.78438 10.32524 4.26% - 1s\n", " 0 0 10.33421 0 433 10.78438 10.33421 4.17% - 1s\n", " 0 0 10.34880 0 412 10.78438 10.34880 4.04% - 1s\n", " 0 0 10.35163 0 426 10.78438 10.35163 4.01% - 1s\n", " 0 0 10.35809 0 503 10.78438 10.35809 3.95% - 1s\n", " 0 2 10.35809 0 503 10.78438 10.35809 3.95% - 3s\n", " 124 133 10.44603 13 375 10.78438 10.36403 3.90% 151 5s\n", "H 143 149 10.7091014 10.36403 3.22% 144 5s\n", "H 181 189 10.6735219 10.36403 2.90% 132 5s\n", "H 238 231 10.6518236 10.36403 2.70% 116 5s\n", "H 244 231 10.6284535 10.36403 2.49% 115 5s\n", "H 405 328 10.6165574 10.37161 2.31% 108 6s\n", "H 519 428 10.6160303 10.37195 2.30% 99.3 6s\n", " 1860 1274 10.55361 35 503 10.61603 10.38491 2.18% 83.1 10s\n", " 1887 1292 10.45514 10 518 10.61603 10.41366 1.91% 81.9 17s\n", " 2132 1434 10.60680 28 282 10.61603 10.42099 1.84% 96.1 20s\n", " 3987 1890 infeasible 30 10.61603 10.43638 1.69% 99.2 25s\n", " 5945 2368 10.48695 31 462 10.61603 10.45163 1.55% 95.9 30s\n", " 8370 3832 10.57026 32 437 10.61603 10.45367 1.53% 94.9 35s\n", " 11416 5222 10.48369 32 352 10.61603 10.46313 1.44% 95.2 40s\n", " 14397 6657 10.51434 32 516 10.61603 10.46749 1.40% 94.5 45s\n", "\n", "Cutting planes:\n", " Gomory: 30\n", " Cover: 6\n", " Implied bound: 1\n", " Clique: 1\n", " MIR: 279\n", " StrongCG: 14\n", " Flow cover: 235\n", " Flow path: 20\n", " GUB cover: 8\n", " Inf proof: 1\n", " Zero half: 11\n", " Network: 28\n", " RLT: 14\n", " Relax-and-lift: 47\n", "\n", "Explored 14620 nodes (1385819 simplex iterations) in 45.09 seconds (42.01 work units)\n", "Thread count was 16 (of 16 available processors)\n", "\n", "Solution count 7: 10.616 10.6166 10.6285 ... 10.7844\n", "\n", "Time limit reached\n", "Best objective 1.061603030595e+01, best bound 1.046749133406e+01, gap 1.3992%\n", "WARNING: Loading a SolverResults object with an 'aborted' status, but\n", "containing a solution\n" ] }, { "data": { "text/plain": [ "SolutionInfo(runtime=45.09699988365173, bound=10.46749133406285, objective=10.616030305953581, relgap=0.013991950626537797, termination='maxTimeLimit')" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solver.solve(\n", " mip_gap=0.005,\n", " time_limit=45,\n", " verbose=True,\n", ")" ] }, { "cell_type": "code", "execution_count": 29, "id": "8afa0765-57cb-4931-be67-cd3f42feae3b", "metadata": {}, "outputs": [], "source": [ "S, G = solver.get_solution(A)" ] }, { "cell_type": "code", "execution_count": 30, "id": "14ff60ea-e44b-4e33-9f7f-de17e0aacdc2", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 134518.0 m(+0) α: 11, β: 9κ = 6, T = 119" ], "text/plain": [ "" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "svgplot(G)" ] }, { "cell_type": "code", "execution_count": 31, "id": "c9406f2c-5431-49fc-8980-d44b6172a43e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.17117956054543038" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - G.size(weight='length')/λ_radial" ] }, { "cell_type": "code", "execution_count": 32, "id": "778e832a-97c2-431f-9c87-46b8e9cbe3e0", "metadata": {}, "outputs": [], "source": [ "with open('yi_2019_κ_6_radial_our.dill', 'wb') as outfile:\n", " dill.dump(G, outfile)" ] } ], "metadata": { "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 5 }