{ "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": { "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": "00e631e4-d82e-40f2-b059-5e2063d66aca", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(0.2, 0.18)" ] }, "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": [], "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": [ "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 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: 0x65002c48\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.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 176 10.78438 9.96630 7.59% - 0s\n", "H 0 0 10.7838118 9.96630 7.58% - 0s\n", "H 0 0 10.7826433 9.96630 7.57% - 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", "H 0 0 10.7785494 10.20597 5.31% - 0s\n", " 0 0 10.20597 0 214 10.77855 10.20597 5.31% - 0s\n", " 0 0 10.25100 0 291 10.77855 10.25100 4.89% - 0s\n", " 0 0 10.25411 0 281 10.77855 10.25411 4.87% - 0s\n", "H 0 0 10.7508027 10.28130 4.37% - 0s\n", " 0 0 10.28130 0 331 10.75080 10.28130 4.37% - 0s\n", "H 0 0 10.7308181 10.28130 4.19% - 0s\n", "H 0 0 10.7308061 10.28130 4.19% - 0s\n", " 0 0 10.28888 0 384 10.73081 10.28888 4.12% - 0s\n", " 0 0 10.31224 0 412 10.73081 10.31224 3.90% - 0s\n", " 0 0 10.31601 0 405 10.73081 10.31601 3.87% - 0s\n", " 0 0 10.32512 0 429 10.73081 10.32512 3.78% - 1s\n", " 0 0 10.32512 0 429 10.73081 10.32512 3.78% - 1s\n", "H 0 0 10.7298197 10.32513 3.77% - 1s\n", "H 0 0 10.6335110 10.32513 2.90% - 1s\n", " 0 2 10.32513 0 429 10.63351 10.32513 2.90% - 2s\n", "H 10 16 10.6269273 10.32694 2.82% 130 2s\n", "H 107 132 10.6069388 10.33078 2.60% 113 3s\n", " 574 479 cutoff 56 10.60694 10.34051 2.51% 73.4 5s\n", " 1757 1307 10.52810 44 499 10.60694 10.36738 2.26% 70.2 12s\n", " 2451 1592 cutoff 29 10.60694 10.38507 2.09% 83.8 15s\n", "H 4540 2397 10.5979851 10.39067 1.96% 77.8 18s\n", "H 4719 2345 10.5883958 10.39067 1.87% 78.0 19s\n", " 5292 2675 10.48365 37 329 10.58840 10.39275 1.85% 77.4 20s\n", "\n", "Cutting planes:\n", " Gomory: 31\n", " Lift-and-project: 8\n", " Cover: 7\n", " Implied bound: 2\n", " MIR: 235\n", " StrongCG: 13\n", " Flow cover: 223\n", " Flow path: 11\n", " GUB cover: 6\n", " Inf proof: 1\n", " Zero half: 6\n", " Mod-K: 2\n", " Network: 14\n", " RLT: 3\n", " Relax-and-lift: 6\n", "\n", "Explored 5397 nodes (419778 simplex iterations) in 20.01 seconds (21.18 work units)\n", "Thread count was 16 (of 16 available processors)\n", "\n", "Solution count 10: 10.5884 10.598 10.6069 ... 10.7785\n", "\n", "Time limit reached\n", "Best objective 1.058839583731e+01, best bound 1.039274956261e+01, gap 1.8477%\n" ] }, { "data": { "text/plain": [ "SolutionInfo(runtime=20.017431020736694, bound=10.392749562605308, objective=10.588395837311046, relgap=0.018477423559886685, 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 918 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.133778131485372" ] }, "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.dill', '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.18, 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": [], "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": [ "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 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: 0x0b20da36\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.07 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 386 10.78438 10.30026 4.49% - 0s\n", " 0 0 10.33638 0 407 10.78438 10.33638 4.15% - 0s\n", " 0 0 10.34419 0 466 10.78438 10.34419 4.08% - 0s\n", " 0 0 10.35800 0 454 10.78438 10.35800 3.95% - 0s\n", " 0 0 10.36209 0 417 10.78438 10.36209 3.92% - 0s\n", " 0 0 10.36516 0 494 10.78438 10.36516 3.89% - 1s\n", " 0 0 10.36516 0 494 10.78438 10.36516 3.89% - 1s\n", " 0 0 10.36516 0 494 10.78438 10.36516 3.89% - 1s\n", " 0 2 10.36516 0 494 10.78438 10.36516 3.89% - 2s\n", " 209 213 10.54179 20 270 10.78438 10.36787 3.86% 120 5s\n", "H 232 229 10.6156510 10.36878 2.33% 121 5s\n", "H 446 413 10.6027805 10.37185 2.18% 115 5s\n", " 1800 1297 10.47211 22 441 10.60278 10.38496 2.05% 90.5 10s\n", " 1854 1376 10.43710 16 558 10.60278 10.42993 1.63% 101 15s\n", " 2988 1650 10.53838 25 298 10.60278 10.44098 1.53% 112 20s\n", "\n", "Cutting planes:\n", " Gomory: 16\n", " Lift-and-project: 4\n", " Cover: 8\n", " Implied bound: 1\n", " MIR: 194\n", " StrongCG: 10\n", " Flow cover: 178\n", " Flow path: 12\n", " GUB cover: 6\n", " Zero half: 5\n", " Network: 30\n", " RLT: 10\n", " Relax-and-lift: 29\n", "\n", "Explored 3016 nodes (341589 simplex iterations) in 20.02 seconds (23.18 work units)\n", "Thread count was 16 (of 16 available processors)\n", "\n", "Solution count 3: 10.6028 10.6157 10.7844 \n", "\n", "Time limit reached\n", "Best objective 1.060278049610e+01, best bound 1.044098394953e+01, gap 1.5260%\n" ] }, { "data": { "text/plain": [ "SolutionInfo(runtime=20.02225613594055, bound=10.440983949525778, objective=10.602780496104984, relgap=0.015259822330438988, 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": [ "Σλ = 136 405 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.15954875643014943" ] }, "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.dill', 'wb'))" ] } ], "metadata": { "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 5 }