{ "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 pickle" ] }, { "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_cvrp\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": {}, "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": "00e631e4-d82e-40f2-b059-5e2063d66aca", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(0.32, 0.29)" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sʹ = hgs_cvrp(A_norm, capacity=6, time_limit=0.5, vehicles=20)\n", "Sʹ.graph['solution_time']" ] }, { "cell_type": "code", "execution_count": 10, "id": "34f6c861-c622-43ee-b667-9340f1b8661e", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 136 877 m(+0) [-1]: 9, [-2]: 11κ = 6, T = 119" ], "text/plain": [ "" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Gʹ = G_from_S(Sʹ, A)\n", "Hʹ = PathFinder(Gʹ, planar=P, A=A).create_detours()\n", "svgplot(Hʹ)" ] }, { "cell_type": "code", "execution_count": 11, "id": "3f23c99d-6818-45cb-b333-293177ceca3c", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.11463530574482794" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - Hʹ.size(weight='length')/λ_branched" ] }, { "cell_type": "code", "execution_count": 12, "id": "6e902710-5a21-4a81-8bae-c7eea9da1489", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter WLSAccessID\n", "Set parameter WLSSecret\n", "Set parameter LicenseID to value 937681\n", "Set parameter MIPFocus to value 1\n", "Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk\n" ] } ], "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": 13, "id": "85fbb9b3-0b62-474d-b05e-1bdb2d630670", "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter TimeLimit to value 20\n", "Set parameter MIPGap to value 0.005\n", "Gurobi Optimizer version 13.0.2 build v13.0.2rc1 (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 20\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 3851 rows, 2592 columns and 14304 nonzeros (Min)\n", "Model fingerprint: 0x8d79edd8\n", "Model has 1296 linear objective coefficients\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 413 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, 2584 iterations, 0.04 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 176 10.78438 9.96630 7.59% - 0s\n", "H 0 0 10.7811045 9.96630 7.56% - 0s\n", "H 0 0 10.7795357 9.96630 7.54% - 0s\n", " 0 0 10.19127 0 232 10.77954 10.19127 5.46% - 0s\n", " 0 0 10.20597 0 214 10.77954 10.20597 5.32% - 0s\n", "H 0 0 10.7785494 10.25069 4.90% - 0s\n", " 0 0 10.25069 0 294 10.77855 10.25069 4.90% - 0s\n", " 0 0 10.25723 0 281 10.77855 10.25723 4.84% - 0s\n", "H 0 0 10.7753028 10.25723 4.81% - 0s\n", "H 0 0 10.7273324 10.25723 4.38% - 0s\n", " 0 0 10.28803 0 308 10.72733 10.28803 4.10% - 0s\n", "H 0 0 10.7263461 10.28803 4.09% - 0s\n", "H 0 0 10.7261654 10.28803 4.08% - 0s\n", " 0 0 10.29462 0 366 10.72617 10.29462 4.02% - 0s\n", " 0 0 10.30371 0 367 10.72617 10.30371 3.94% - 0s\n", "H 0 0 10.7027515 10.30861 3.68% - 0s\n", " 0 0 10.30861 0 406 10.70275 10.30861 3.68% - 0s\n", " 0 0 10.31338 0 415 10.70275 10.31338 3.64% - 0s\n", " 0 0 10.31338 0 415 10.70275 10.31338 3.64% - 0s\n", " 0 0 10.31338 0 413 10.70275 10.31338 3.64% - 0s\n", "H 0 0 10.6956337 10.31338 3.57% - 1s\n", "H 0 0 10.6941302 10.31338 3.56% - 1s\n", "H 0 0 10.6941182 10.31338 3.56% - 1s\n", "H 0 0 10.6741297 10.31338 3.38% - 1s\n", " 0 2 10.31338 0 413 10.67413 10.31338 3.38% - 3s\n", "H 149 152 10.5936841 10.32702 2.52% 127 4s\n", "H 152 155 10.5863545 10.32702 2.45% 125 4s\n", "H 220 193 10.5858274 10.32776 2.44% 106 4s\n", " 601 475 10.48054 23 236 10.58583 10.32921 2.42% 82.0 5s\n", " 1788 1277 10.47471 21 503 10.58583 10.37664 1.98% 65.8 10s\n", " 1994 1429 10.41075 20 501 10.58583 10.38260 1.92% 80.6 15s\n", " 4368 2227 10.48230 29 242 10.58583 10.39241 1.83% 89.8 20s\n", "\n", "Cutting planes:\n", " Gomory: 22\n", " Lift-and-project: 12\n", " Cover: 10\n", " Implied bound: 1\n", " MIR: 239\n", " StrongCG: 15\n", " Flow cover: 201\n", " Flow path: 13\n", " GUB cover: 7\n", " Zero half: 5\n", " Mod-K: 5\n", " Network: 17\n", " Relax-and-lift: 9\n", "\n", "Explored 4389 nodes (398510 simplex iterations) in 20.01 seconds (22.94 work units)\n", "Thread count was 16 (of 16 available processors)\n", "\n", "Solution count 10: 10.5858 10.5864 10.5937 ... 10.7263\n", "\n", "Time limit reached\n", "Best objective 1.058582742936e+01, best bound 1.039241405855e+01, gap 1.8271%\n" ] }, { "data": { "text/plain": [ "SolutionInfo(runtime=20.016806840896606, bound=10.392414058546652, objective=10.585827429361387, relgap=0.01827097334671013, termination='maxTimeLimit')" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solver.solve(\n", " mip_gap=0.005,\n", " time_limit=20,\n", " verbose=True,\n", " options=dict(mipfocus=1),\n", ")" ] }, { "cell_type": "code", "execution_count": 14, "id": "0d2150b7-4911-4576-820e-55ee5c89460b", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 133 885 m(+0) [-1]: 10, [-2]: 10κ = 6, T = 119" ], "text/plain": [ "" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S, G = solver.get_solution(A)\n", "svgplot(G)" ] }, { "cell_type": "code", "execution_count": 15, "id": "2b1b17e1-c564-40ee-a011-86ee7a3fd3a3", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.13398784961608867" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - G.size(weight='length')/λ_branched" ] }, { "cell_type": "code", "execution_count": 16, "id": "c9ac92f6-8f87-49b5-a74b-d3576a301d4d", "metadata": {}, "outputs": [], "source": [ "pickle.dump(G, open('yi_2019_κ_6_branched_our.pkl', 'wb'))" ] }, { "cell_type": "markdown", "id": "1313de7c-2c1f-4cf9-9a11-12e6eee34827", "metadata": {}, "source": [ "## Solve κ = 6 (radial)" ] }, { "cell_type": "code", "execution_count": 17, "id": "295267e7-4927-4d32-8480-998ea7ceebae", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(0.33, 0.16)" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sʹ = hgs_cvrp(A_norm, capacity=6, time_limit=0.5, vehicles=20)\n", "Sʹ.graph['solution_time']" ] }, { "cell_type": "code", "execution_count": 18, "id": "e3117828-8c09-4677-840b-a358dcfe9fe6", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 136 877 m(+0) [-1]: 9, [-2]: 11κ = 6, T = 119" ], "text/plain": [ "" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Gʹ = G_from_S(Sʹ, A)\n", "Hʹ = PathFinder(Gʹ, planar=P, A=A).create_detours()\n", "svgplot(Hʹ)" ] }, { "cell_type": "code", "execution_count": 19, "id": "5faee4a5-6dab-4d01-8b79-dae262635db1", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.15663966893499937" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - Hʹ.size(weight='length')/λ_radial" ] }, { "cell_type": "code", "execution_count": 20, "id": "dcdc23dc-1a0e-4c2d-8934-73cbc5e5fe2f", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter WLSAccessID\n", "Set parameter WLSSecret\n", "Set parameter LicenseID to value 937681\n", "Set parameter MIPFocus to value 1\n", "Academic license 937681 - for non-commercial use only - registered to ma___@dtu.dk\n" ] } ], "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": 21, "id": "5f7d4e0d-e58c-4abf-b988-fabd9c66331e", "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter TimeLimit to value 20\n", "Set parameter MIPGap to value 0.005\n", "Gurobi Optimizer version 13.0.2 build v13.0.2rc1 (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 20\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 3970 rows, 2592 columns and 15362 nonzeros (Min)\n", "Model fingerprint: 0x28e963e0\n", "Model has 1296 linear objective coefficients\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 413 rows and 0 columns\n", "Presolve time: 0.02s\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, 2894 iterations, 0.06 seconds (0.08 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 271 10.78438 9.99381 7.33% - 0s\n", " 0 0 10.23002 0 275 10.78438 10.23002 5.14% - 0s\n", " 0 0 10.24150 0 235 10.78438 10.24150 5.03% - 0s\n", " 0 0 10.29047 0 421 10.78438 10.29047 4.58% - 0s\n", " 0 0 10.30026 0 387 10.78438 10.30026 4.49% - 0s\n", " 0 0 10.33105 0 349 10.78438 10.33105 4.20% - 0s\n", " 0 0 10.34404 0 410 10.78438 10.34404 4.08% - 0s\n", " 0 0 10.35894 0 441 10.78438 10.35894 3.95% - 1s\n", " 0 0 10.36245 0 454 10.78438 10.36245 3.91% - 1s\n", " 0 0 10.36781 0 511 10.78438 10.36781 3.86% - 1s\n", " 0 0 10.36781 0 508 10.78438 10.36781 3.86% - 1s\n", " 0 2 10.36791 0 508 10.78438 10.36791 3.86% - 2s\n", " 215 231 10.56143 22 354 10.78438 10.37662 3.78% 142 5s\n", "H 1032 786 10.7050175 10.38491 2.99% 101 9s\n", " 1452 1082 10.42692 24 431 10.70502 10.38785 2.96% 93.7 10s\n", "H 1699 1149 10.6880722 10.38925 2.80% 90.3 12s\n", " 1716 1160 10.62642 22 513 10.68807 10.41105 2.59% 89.4 17s\n", " 2045 1368 10.56994 29 389 10.68807 10.41733 2.53% 112 20s\n", "\n", "Cutting planes:\n", " Gomory: 17\n", " Lift-and-project: 3\n", " Cover: 5\n", " Implied bound: 5\n", " MIR: 155\n", " StrongCG: 4\n", " Flow cover: 127\n", " Flow path: 1\n", " GUB cover: 4\n", " Zero half: 1\n", " Mod-K: 2\n", " Network: 20\n", " RLT: 8\n", " Relax-and-lift: 17\n", "\n", "Explored 2064 nodes (238443 simplex iterations) in 20.01 seconds (23.04 work units)\n", "Thread count was 16 (of 16 available processors)\n", "\n", "Solution count 3: 10.6881 10.705 10.7844 \n", "\n", "Time limit reached\n", "Best objective 1.068807224015e+01, best bound 1.041733142791e+01, gap 2.5331%\n" ] }, { "data": { "text/plain": [ "SolutionInfo(runtime=20.01891589164734, bound=10.417331427908284, objective=10.688072240152739, relgap=0.025331117357846877, termination='maxTimeLimit')" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solver.solve(\n", " mip_gap=0.005,\n", " time_limit=20,\n", " verbose=True,\n", " options=dict(mipfocus=1),\n", ")" ] }, { "cell_type": "code", "execution_count": 22, "id": "09fe9110-b882-4fc3-b137-62d8c084f5d4", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "Σλ = 134 966 m(+0) [-1]: 10, [-2]: 10κ = 6, T = 119" ], "text/plain": [ "" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S, G = solver.get_solution(A)\n", "svgplot(G)" ] }, { "cell_type": "code", "execution_count": 23, "id": "c9406f2c-5431-49fc-8980-d44b6172a43e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.16841447876500804" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1 - G.size(weight='length')/λ_radial" ] }, { "cell_type": "code", "execution_count": 24, "id": "778e832a-97c2-431f-9c87-46b8e9cbe3e0", "metadata": {}, "outputs": [], "source": [ "pickle.dump(G, open('yi_2019_κ_6_radial_our.pkl', 'wb'))" ] } ], "metadata": { "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 5 }