{ "cells": [ { "cell_type": "markdown", "id": "9348fee9-c086-4771-b9fc-034026fbca7c", "metadata": {}, "source": [ "# 3.6.1 Yi et at 2019" ] }, { "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.4, 0.19)" ] }, "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: 0xcba7b093\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, 2583 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.7838118 9.96630 7.58% - 0s\n", "H 0 0 10.7811045 9.96630 7.56% - 0s\n", " 0 0 10.19355 0 253 10.78110 10.19355 5.45% - 0s\n", "H 0 0 10.7810924 10.19355 5.45% - 0s\n", " 0 0 10.21049 0 278 10.78109 10.21049 5.29% - 0s\n", "H 0 0 10.7801181 10.21049 5.28% - 0s\n", " 0 0 10.23879 0 321 10.78012 10.23879 5.02% - 0s\n", "H 0 0 10.7795237 10.25316 4.88% - 0s\n", " 0 0 10.25316 0 360 10.77952 10.25316 4.88% - 0s\n", "H 0 0 10.7785494 10.25316 4.87% - 0s\n", " 0 0 10.29090 0 373 10.77855 10.29090 4.52% - 0s\n", "H 0 0 10.7499115 10.29090 4.27% - 0s\n", " 0 0 10.29297 0 370 10.74991 10.29297 4.25% - 0s\n", " 0 0 10.30518 0 428 10.74991 10.30518 4.14% - 1s\n", " 0 0 10.31095 0 393 10.74991 10.31095 4.08% - 1s\n", " 0 0 10.31744 0 404 10.74991 10.31744 4.02% - 1s\n", "H 0 0 10.7498995 10.31744 4.02% - 1s\n", "H 0 0 10.7298198 10.31744 3.84% - 1s\n", "H 0 0 10.7098313 10.31744 3.66% - 1s\n", "H 0 0 10.7046838 10.31744 3.62% - 2s\n", "H 0 0 10.7032476 10.31744 3.60% - 2s\n", "H 0 0 10.6862326 10.31744 3.45% - 2s\n", " 0 2 10.31744 0 404 10.68623 10.31744 3.45% - 3s\n", "H 2 4 10.6789043 10.31760 3.38% 39.5 3s\n", "H 38 47 10.5988086 10.32040 2.63% 106 3s\n", "H 95 110 10.5973051 10.32040 2.61% 83.4 3s\n", "H 101 110 10.5882100 10.32040 2.53% 82.3 3s\n", " 502 418 10.37280 9 378 10.58821 10.32465 2.49% 59.3 5s\n", " 1780 1381 10.50956 24 470 10.58821 10.34722 2.28% 46.5 10s\n", " 1815 1422 10.36715 16 548 10.58821 10.36681 2.09% 53.4 15s\n", " 3418 2092 10.50582 59 316 10.58821 10.37819 1.98% 73.0 20s\n", " 6337 3467 10.43055 17 434 10.58821 10.37819 1.98% 72.9 25s\n", " 8389 4848 10.40273 26 469 10.58821 10.38048 1.96% 74.2 30s\n", " 11369 7210 10.49668 51 271 10.58821 10.38631 1.91% 74.2 35s\n", " 14890 9478 10.51558 27 277 10.58821 10.39555 1.82% 74.3 40s\n", " 19040 12379 10.46359 50 275 10.58821 10.39802 1.80% 73.8 45s\n", "\n", "Cutting planes:\n", " Gomory: 33\n", " Lift-and-project: 11\n", " Cover: 12\n", " MIR: 309\n", " StrongCG: 22\n", " Flow cover: 262\n", " Flow path: 22\n", " GUB cover: 3\n", " Inf proof: 2\n", " Zero half: 5\n", " Mod-K: 2\n", " Network: 23\n", " RLT: 1\n", " Relax-and-lift: 19\n", "\n", "Explored 19359 nodes (1426603 simplex iterations) in 45.07 seconds (40.81 work units)\n", "Thread count was 16 (of 16 available processors)\n", "\n", "Solution count 10: 10.5882 10.5973 10.5988 ... 10.7499\n", "\n", "Time limit reached\n", "Best objective 1.058820995844e+01, best bound 1.039802485227e+01, gap 1.7962%\n", "WARNING: Loading a SolverResults object with an 'aborted' status, but\n", "containing a solution\n" ] }, { "data": { "text/plain": [ "SolutionInfo(runtime=45.0789999961853, bound=10.398024852271213, objective=10.588209958443283, relgap=0.017961969673675804, 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", " options=dict(mipfocus=1),\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.43, 0.19)" ] }, "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: 0x66fae53e\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, 2717 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.23156 0 312 10.78438 10.23156 5.13% - 0s\n", " 0 0 10.23895 0 213 10.78438 10.23895 5.06% - 0s\n", " 0 0 10.28063 0 428 10.78438 10.28063 4.67% - 0s\n", " 0 0 10.28480 0 463 10.78438 10.28480 4.63% - 0s\n", " 0 0 10.31555 0 373 10.78438 10.31555 4.35% - 1s\n", " 0 0 10.32560 0 378 10.78438 10.32560 4.25% - 1s\n", " 0 0 10.33688 0 506 10.78438 10.33688 4.15% - 1s\n", " 0 0 10.34033 0 527 10.78438 10.34033 4.12% - 1s\n", " 0 0 10.34858 0 531 10.78438 10.34858 4.04% - 1s\n", " 0 2 10.34858 0 531 10.78438 10.34858 4.04% - 3s\n", " 130 156 10.46052 16 460 10.78438 10.35578 3.97% 158 5s\n", "H 491 420 10.7481569 10.36319 3.58% 108 7s\n", "H 769 585 10.7465553 10.36589 3.54% 98.6 8s\n", "H 785 611 10.7346593 10.36589 3.44% 98.2 8s\n", "H 961 619 10.6529319 10.36653 2.69% 94.7 9s\n", " 1097 751 10.44789 24 353 10.65293 10.36653 2.69% 92.9 10s\n", " 1933 1249 10.56392 24 267 10.65293 10.37083 2.65% 84.9 15s\n", "H 1949 1196 10.6165820 10.40574 1.99% 84.2 16s\n", "H 1949 1136 10.6160549 10.40574 1.98% 84.2 16s\n", " 1956 1141 10.61605 18 588 10.61605 10.41279 1.91% 83.9 22s\n", " 2361 1298 cutoff 32 10.61605 10.43016 1.75% 97.7 25s\n", " 3822 1762 10.60183 57 159 10.61605 10.44196 1.64% 101 30s\n", " 6364 2803 10.53591 27 344 10.61605 10.45398 1.53% 96.2 35s\n", " 8725 4141 10.54727 32 398 10.61605 10.46102 1.46% 97.0 40s\n", " 11636 5553 10.50132 31 369 10.61605 10.46639 1.41% 96.5 45s\n", "\n", "Cutting planes:\n", " Gomory: 22\n", " Cover: 4\n", " Implied bound: 2\n", " Clique: 2\n", " MIR: 284\n", " StrongCG: 12\n", " Flow cover: 230\n", " Flow path: 19\n", " GUB cover: 7\n", " Zero half: 8\n", " Network: 20\n", " RLT: 8\n", " Relax-and-lift: 34\n", "\n", "Explored 11661 nodes (1130643 simplex iterations) in 45.09 seconds (43.12 work units)\n", "Thread count was 16 (of 16 available processors)\n", "\n", "Solution count 7: 10.6161 10.6166 10.6529 ... 10.7844\n", "\n", "Time limit reached\n", "Best objective 1.061605486611e+01, best bound 1.046638765619e+01, gap 1.4098%\n", "WARNING: Loading a SolverResults object with an 'aborted' status, but\n", "containing a solution\n" ] }, { "data": { "text/plain": [ "SolutionInfo(runtime=45.09099984169006, bound=10.466387656186585, objective=10.61605486611012, relgap=0.014098194838962352, 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", " options=dict(mipfocus=1),\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": [ "Σλ = 134592.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.17072176123560445" ] }, "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 }