{ "cells": [ { "cell_type": "markdown", "id": "1e7b1bae-732a-45a3-b6ff-aa0a4c46b8b4", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "# 3.3/4/5 Impact/Comparison/Dealing" ] }, { "cell_type": "markdown", "id": "32fa66db-1a88-4268-85bb-e1f69a80103c", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "Sections covered:\n", "- 3.3: Impact of detours on the solver’s total length\n", "- 3.4: Comparison of B&C and HGS solutions\n", "- 3.5: Dealing with crossings from HGS-CVRP" ] }, { "cell_type": "markdown", "id": "18d1bf89-4d35-4353-8c13-bf659ee7a93a", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "This is used in the paper **Flexible cable routing framework for wind farm collection system optimization**." ] }, { "cell_type": "markdown", "id": "e238e453-c1fe-42e1-9640-066aed035fbb", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "## Preamble" ] }, { "cell_type": "code", "execution_count": 1, "id": "218c6fb9-f3e0-4a6f-82ff-8b3cfa9a00bd", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "import urllib.request\n", "import lzma\n", "import shutil\n", "import os\n", "from pathlib import Path\n", "import numpy as np\n", "import polars as pl" ] }, { "cell_type": "code", "execution_count": 2, "id": "0623226d-b7ad-4632-a3d2-c39865530dae", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "from optiwindnet.db import database_connection, G_from_routeset, NodeSet, RouteSet, Method\n", "from optiwindnet.svg import svgplot" ] }, { "cell_type": "code", "execution_count": 3, "id": "f98054f3-2a88-4c4f-b2a5-756235de02cd", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "from matplotlib.lines import Line2D\n", "\n", "%config InlineBackend.figure_formats = ['svg']\n", "plt.rcParams['svg.fonttype'] = 'none'\n", "\n", "style_file = Path('mplstyles/jupyter_dark.mplstyle')\n", "style_file.is_file() and plt.style.use(style_file)\n", "pub_style_file = Path('mplstyles/pdf_1col.mplstyle')\n", "pub_style = pub_style_file if pub_style_file.is_file() else 'default'" ] }, { "cell_type": "markdown", "id": "a1192c1f-b708-4fc5-b927-b072987a7503", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "## Setup" ] }, { "cell_type": "code", "execution_count": 4, "id": "d0d97d97-0313-47df-8c82-a06d6e0cc668", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "def fetch_zenodo_file(record, file_name, target_path: str = '.'):\n", " url = f'https://zenodo.org/records/{record}/files/{file_name}.xz?download=1'\n", " try:\n", " with open(os.path.join(target_path, file_name), 'xb') as f_out:\n", " with urllib.request.urlopen(url) as response:\n", " with lzma.open(response) as decompressor:\n", " shutil.copyfileobj(decompressor, f_out)\n", " except FileExistsError:\n", " return" ] }, { "cell_type": "code", "execution_count": 5, "id": "39336d4b-3403-4375-92b6-16ba9ac0a33e", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "record = '19798734'\n", "DB_FILE = 'paperdb.v4.sqlite'" ] }, { "cell_type": "code", "execution_count": 6, "id": "ffcfdf79-9aa0-4362-9513-82bd276ed2f6", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "fetch_zenodo_file(record, DB_FILE)" ] }, { "cell_type": "markdown", "id": "63c26f77-8bc7-4ef3-884d-a0102094421a", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "## Selecting *actual* routesets" ] }, { "cell_type": "code", "execution_count": 7, "id": "1b98441f-8632-470a-be83-10f85d2f0de7", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "69" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "with database_connection(DB_FILE):\n", " Ns_q = NodeSet.select().where(~NodeSet.name.startswith('!'))\n", "Ns_q.count()" ] }, { "cell_type": "code", "execution_count": 8, "id": "94752565-3f6a-41f5-91c6-e80e861f8fcf", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "1464" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "entries = []\n", "for ns in Ns_q:\n", " for rs in ns.routesets:\n", " entries.append((\n", " ns.name,\n", " rs.id,\n", " ns.T,\n", " rs.capacity,\n", " rs.detextra,\n", " rs.length,\n", " rs.creator,\n", " rs.misc.get('gap', None),\n", " ))\n", "len(entries)" ] }, { "cell_type": "markdown", "id": "403330f7-27e0-4619-8556-7301a6435b4d", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "### Make DataFrame" ] }, { "cell_type": "code", "execution_count": 9, "id": "51c897cf-f2f4-45fa-96de-4253a21e91bd", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "schema_actual = dict(\n", " name=str,\n", " id=int,\n", " T=int,\n", " capacity=int,\n", " detextra=float,\n", " length=float,\n", " creator=str,\n", " gap=float,\n", ")" ] }, { "cell_type": "code", "execution_count": 10, "id": "483b7e3b-feea-43c9-abb8-846a958c5981", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "df_actual = pl.DataFrame(entries, schema=schema_actual, orient='row')" ] }, { "cell_type": "code", "execution_count": 11, "id": "d41dcad5-4bb9-4c74-9c8f-9d11f354dbc3", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/html": [ "
\n", "shape: (1_464, 8)
nameidTcapacitydetextralengthcreatorgap
stri64i64i64f64f64strf64
"Gode Wind 1"15550.00084763626.868227"MILP.pyomo.cplex"0.004949
"Gode Wind 1"2557null55566.023496"MILP.pyomo.cplex"0.004982
"Gode Wind 1"3556null59109.208596"MILP.pyomo.cplex"0.005
"Gode Wind 1"4559null51675.248009"MILP.pyomo.cplex"0.005
"Gode Wind 1"5558null53268.425754"MILP.pyomo.cplex"0.004997
……………………
"Cazzaro-2022"2163050100.07.876699"MILP.pyomo.cplex"0.00496
"Cazzaro-2022"2163150112.2204e-167.71745"MILP.pyomo.cplex"0.004993
"Cazzaro-2022"216325080.08.425937"MILP.pyomo.cplex"0.004999
"Cazzaro-2022"216335012-1.1102e-167.630594"MILP.pyomo.cplex"0.004999
"Cazzaro-2022"225465040.10266111.920841"MILP.pyomo.gurobi"0.000732
" ], "text/plain": [ "shape: (1_464, 8)\n", "┌──────────────┬───────┬─────┬──────────┬─────────────┬──────────────┬──────────────────┬──────────┐\n", "│ name ┆ id ┆ T ┆ capacity ┆ detextra ┆ length ┆ creator ┆ gap │\n", "│ --- ┆ --- ┆ --- ┆ --- ┆ --- ┆ --- ┆ --- ┆ --- │\n", "│ str ┆ i64 ┆ i64 ┆ i64 ┆ f64 ┆ f64 ┆ str ┆ f64 │\n", "╞══════════════╪═══════╪═════╪══════════╪═════════════╪══════════════╪══════════════════╪══════════╡\n", "│ Gode Wind 1 ┆ 1 ┆ 55 ┆ 5 ┆ 0.000847 ┆ 63626.868227 ┆ MILP.pyomo.cplex ┆ 0.004949 │\n", "│ Gode Wind 1 ┆ 2 ┆ 55 ┆ 7 ┆ null ┆ 55566.023496 ┆ MILP.pyomo.cplex ┆ 0.004982 │\n", "│ Gode Wind 1 ┆ 3 ┆ 55 ┆ 6 ┆ null ┆ 59109.208596 ┆ MILP.pyomo.cplex ┆ 0.005 │\n", "│ Gode Wind 1 ┆ 4 ┆ 55 ┆ 9 ┆ null ┆ 51675.248009 ┆ MILP.pyomo.cplex ┆ 0.005 │\n", "│ Gode Wind 1 ┆ 5 ┆ 55 ┆ 8 ┆ null ┆ 53268.425754 ┆ MILP.pyomo.cplex ┆ 0.004997 │\n", "│ … ┆ … ┆ … ┆ … ┆ … ┆ … ┆ … ┆ … │\n", "│ Cazzaro-2022 ┆ 21630 ┆ 50 ┆ 10 ┆ 0.0 ┆ 7.876699 ┆ MILP.pyomo.cplex ┆ 0.00496 │\n", "│ Cazzaro-2022 ┆ 21631 ┆ 50 ┆ 11 ┆ 2.2204e-16 ┆ 7.71745 ┆ MILP.pyomo.cplex ┆ 0.004993 │\n", "│ Cazzaro-2022 ┆ 21632 ┆ 50 ┆ 8 ┆ 0.0 ┆ 8.425937 ┆ MILP.pyomo.cplex ┆ 0.004999 │\n", "│ Cazzaro-2022 ┆ 21633 ┆ 50 ┆ 12 ┆ -1.1102e-16 ┆ 7.630594 ┆ MILP.pyomo.cplex ┆ 0.004999 │\n", "│ Cazzaro-2022 ┆ 22546 ┆ 50 ┆ 4 ┆ 0.102661 ┆ 11.920841 ┆ MILP.pyomo.gurob ┆ 0.000732 │\n", "│ ┆ ┆ ┆ ┆ ┆ ┆ i ┆ │\n", "└──────────────┴───────┴─────┴──────────┴─────────────┴──────────────┴──────────────────┴──────────┘" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df_actual" ] }, { "cell_type": "code", "execution_count": 12, "id": "8b2bdc2b-b997-4c73-8c73-8c705cea7bf7", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/html": [ "
\n", "shape: (69, 2)
namecount
stru32
"Humber Gateway"22
"Gemini 1"22
"Gemini 2"22
"Thanet"22
"Taylor-2023.1_OSS"22
……
"CECEP Yangjiang Nanpeng Island"22
"SPIC Binhai North H2"22
"Nordsee One"22
"Rudong H8"22
"Meerwind"22
" ], "text/plain": [ "shape: (69, 2)\n", "┌────────────────────────────────┬───────┐\n", "│ name ┆ count │\n", "│ --- ┆ --- │\n", "│ str ┆ u32 │\n", "╞════════════════════════════════╪═══════╡\n", "│ Humber Gateway ┆ 22 │\n", "│ Gemini 1 ┆ 22 │\n", "│ Gemini 2 ┆ 22 │\n", "│ Thanet ┆ 22 │\n", "│ Taylor-2023.1_OSS ┆ 22 │\n", "│ … ┆ … │\n", "│ CECEP Yangjiang Nanpeng Island ┆ 22 │\n", "│ SPIC Binhai North H2 ┆ 22 │\n", "│ Nordsee One ┆ 22 │\n", "│ Rudong H8 ┆ 22 │\n", "│ Meerwind ┆ 22 │\n", "└────────────────────────────────┴───────┘" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df_actual['name'].value_counts()" ] }, { "cell_type": "code", "execution_count": 13, "id": "9d453f3d-967d-4f07-913f-0ddef106638f", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "0.019817266284630097" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df_actual['gap'].max()" ] }, { "cell_type": "code", "execution_count": 14, "id": "1ee737e3-0d82-4ae2-bce8-af1603b70ea2", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "0.12263549531666174" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df_actual['detextra'].max()" ] }, { "cell_type": "markdown", "id": "1108f043-659e-4085-a4be-1571d5f7a7cc", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "### group ⟨heuri, exact⟩ pairs" ] }, { "cell_type": "code", "execution_count": 15, "id": "bc71e27c-3983-4fc4-9263-db4496774be5", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "732" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pairs_actual = []\n", "for ns in Ns_q:\n", " dfn = df_actual.filter(pl.col('name') == ns.name)\n", " for k in range(dfn['capacity'].min(), dfn['capacity'].max() + 1):\n", " dfk = dfn.filter(pl.col('capacity') == k)\n", " if dfk.height >= 2:\n", " mask = pl.col('creator') == 'baselines.hgs'\n", " heuri = dfk.filter(mask).bottom_k(1, by='length')[0]\n", " exact = dfk.filter(~mask).bottom_k(1, by='gap')[0]\n", " if exact['gap'].item() <= 0.02:\n", " pairs_actual.append((RouteSet.get_by_id(heuri['id'].item()),\n", " RouteSet.get_by_id(exact['id'].item())))\n", "len(pairs_actual)" ] }, { "cell_type": "code", "execution_count": 16, "id": "5cac2789-7332-4797-b72e-6448f64df099", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "diffs = []\n", "for rs_hgs, rs_bnc in pairs_actual:\n", " diffs.append(rs_hgs.length/rs_bnc.length - 1)" ] }, { "cell_type": "code", "execution_count": 17, "id": "bfd7e572-05e0-4937-b502-89b1578816bf", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "21311 22196 Sandbank\n", "21545 21925 Moray West.1_OSS\n" ] } ], "source": [ "for (heuri, exact), diff in zip(pairs_actual, diffs):\n", " if diff >= 0.07:\n", " print(heuri.id, exact.id, exact.nodes.name)" ] }, { "cell_type": "code", "execution_count": 18, "id": "95f4b443-2648-4ddf-af3b-29055dd5aec8", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "540" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "small_diffs = []\n", "for (heuri, exact), diff in zip(pairs_actual, diffs):\n", " if diff <= 0.01:\n", " small_diffs.append((heuri.id, exact.id))\n", "len(small_diffs)" ] }, { "cell_type": "code", "execution_count": 19, "id": "2fdc23b4-e950-415b-bc80-24c3c653759e", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.07397519014347398\n" ] }, { "data": { "image/svg+xml": [ "Σλ = 94 338 m(+0) [-1]: 9κ = 8, T = 72" ], "text/plain": [ "" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "rs = RouteSet.get_by_id(21311)\n", "print(rs.detextra)\n", "svgplot(G_from_routeset(rs))" ] }, { "cell_type": "code", "execution_count": 20, "id": "a1908c87-bd2b-4099-b310-d9ba7d729596", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.0013995437575948788\n" ] }, { "data": { "image/svg+xml": [ "Σλ = 87 425 m(+1) [-1]: 10κ = 8, T = 72" ], "text/plain": [ "" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "rs = RouteSet.get_by_id(22196)\n", "print(rs.detextra)\n", "svgplot(G_from_routeset(rs))" ] }, { "cell_type": "code", "execution_count": 21, "id": "1c5dac30-e7c0-4fe1-9b38-1c491adaabec", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.02038470064164777\n" ] }, { "data": { "image/svg+xml": [ "Σλ = 96 524 m(+0) [-1]: 5κ = 12, T = 60" ], "text/plain": [ "" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "rs = RouteSet.get_by_id(21545)\n", "print(rs.detextra)\n", "svgplot(G_from_routeset(rs))" ] }, { "cell_type": "code", "execution_count": 22, "id": "ec1926d1-0b65-4407-8947-52294076f172", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "None\n" ] }, { "data": { "image/svg+xml": [ "Σλ = 89 697 m(+1) [-1]: 6κ = 12, T = 60" ], "text/plain": [ "" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "rs = RouteSet.get_by_id(21925)\n", "print(rs.detextra)\n", "svgplot(G_from_routeset(rs))" ] }, { "cell_type": "code", "execution_count": 23, "id": "06bc5c03-4aaf-49a6-b3bc-5318c31ea82b", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", " \n", " image/svg+xml\n", " \n", " \n", " OptiWindNet\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.00\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.01\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.02\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.03\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.04\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.05\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.06\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.07\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.08\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 50\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 100\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 150\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 200\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \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": [ "plt.hist(diffs, bins=21);" ] }, { "cell_type": "markdown", "id": "cade026b-c066-4711-af63-2da05401c1d7", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "## HGS optimizer" ] }, { "cell_type": "markdown", "id": "599ebd66-403e-4196-a071-e87a7e985ee4", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "### Select HGS-CVRP entries" ] }, { "cell_type": "code", "execution_count": 24, "id": "6c8d5ba0-fe15-4772-858f-af5834062bee", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "method_hgs = Method.select().where(\n", " Method.funname == 'hgs_cvrp',\n", " Method.options['timeLimit'] == 120\n", ")\n", "method_hgs.count()" ] }, { "cell_type": "code", "execution_count": 25, "id": "6155b451-8280-4796-ae0c-d46c00856847", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "hgs_cvrp {'complete': False, 'lambda_': 40, 'mu': 25, 'nbClose': 5, 'nbElite': 4, 'nbGranular': 20, 'nbIter': 20000, 'scale': 10000.0, 'seed': 0, 'targetFeasible': 0.2, 'timeLimit': 120.0, 'useSwapStar': True}\n", "hgs_cvrp {'complete': False, 'lambda_': 40, 'mu': 25, 'nbClose': 5, 'nbElite': 4, 'nbGranular': 20, 'nbIter': 20000, 'seed': 20241113, 'targetFeasible': 0.2, 'timeLimit': 120, 'useSwapStar': True}\n" ] } ], "source": [ "for m in method_hgs:\n", " print(m.funname, m.options)" ] }, { "cell_type": "markdown", "id": "4f443f69-7542-46a9-bcfe-bf8a986f2551", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "### synthetic instances (a single capacity per NodeSet)" ] }, { "cell_type": "code", "execution_count": 26, "id": "dc4d189e-bbd9-43a0-a921-405157b10015", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "pairs_synth = []" ] }, { "cell_type": "code", "execution_count": 27, "id": "a85bc4bf-7f79-413b-a6dd-917e5de3c2bd", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "(2346, 2346)" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# hgs instances that were first solved by cplex\n", "hgs_sub2 = (RouteSet.select()\n", " .join(NodeSet)\n", " .switch(RouteSet)\n", " .where(\n", " RouteSet.method.in_([m.digest for m in method_hgs]),\n", " RouteSet.misc['solver_details'].is_null(False),\n", " RouteSet.misc['solver_details']['incumbent_id'].is_null(False),\n", " NodeSet.name.startswith('!'),\n", " NodeSet.T >= 50,\n", " ))\n", "# keep only instances for which the exact solution is within 2% gap\n", "for rs_hgs in hgs_sub2:\n", " rs_bnc = RouteSet.get_by_id(rs_hgs.misc['solver_details']['incumbent_id'])\n", " if rs_bnc.misc['gap'] <= 0.02:\n", " pairs_synth.append((rs_hgs, rs_bnc))\n", "hgs_sub2.count(), len(pairs_synth)" ] }, { "cell_type": "code", "execution_count": 28, "id": "b77a4611-f9f5-4561-a496-d9917b842ee9", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "(4033, 6379)" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# hgs instances that were solved by cplex afterward\n", "hgs_sub2_ = (RouteSet.select()\n", " .join(NodeSet)\n", " .switch(RouteSet)\n", " .where(\n", " RouteSet.method.in_([m.digest for m in method_hgs]),\n", " RouteSet.misc['solver_details'].is_null(),\n", " NodeSet.name.startswith('!'),\n", " NodeSet.T >= 50,\n", " ))\n", "# keep only instances for which the exact solution is within 2% gap\n", "for rs_hgs in hgs_sub2_:\n", " if rs_hgs.nodes.routesets.count() == 1:\n", " # no MILP counterpart\n", " continue\n", " cplex = gurobi = None\n", " for rs2 in rs_hgs.nodes.routesets:\n", " if rs2.id == rs_hgs.id:\n", " continue\n", " if rs2.creator == 'MILP.pyomo.cplex':\n", " cplex = rs2\n", " elif rs2.creator == 'MILP.pyomo.gurobi':\n", " gurobi = rs2\n", " if gurobi and gurobi.misc['gap'] <= 0.02:\n", " pairs_synth.append((rs_hgs, gurobi))\n", " elif cplex and cplex.misc['gap'] <= 0.02:\n", " pairs_synth.append((rs_hgs, cplex))\n", "hgs_sub2_.count(), len(pairs_synth)" ] }, { "cell_type": "code", "execution_count": 29, "id": "a824ae0b-f972-495b-9160-326d1de6ecd1", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "7111" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(pairs_actual) + len(pairs_synth)" ] }, { "cell_type": "markdown", "id": "e92cd6b7-dd3b-40d7-92a6-924f0e02d91c", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "### Check if there are NodeSets counted multiple times" ] }, { "cell_type": "code", "execution_count": 30, "id": "cf32f6eb-bb5e-412e-a8a5-89d3edd039e5", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "6379" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(pairs_synth)" ] }, { "cell_type": "code", "execution_count": 31, "id": "73a4b8e1-763e-48da-a916-635aef966f7d", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "(6379, 0)" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "once = set()\n", "twice = set()\n", "for rs_hgs, rs_bnc in pairs_synth:\n", " assert rs_hgs.nodes_id == rs_bnc.nodes_id, (rs_hgs.nodes.name, rs_bnc.nodes.name)\n", " if rs_hgs.nodes_id in once:\n", " if rs_hgs.nodes_id in twice:\n", " print(f'more than twice: {rs_hgs.nodes.name}')\n", " twice.add(rs_hgs.nodes_id)\n", " else:\n", " once.add(rs_hgs.nodes_id)\n", "len(once), len(twice)" ] }, { "cell_type": "markdown", "id": "5f9b2e98-4fd0-496c-8864-3cc0239b99fe", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "### Make DataFrame" ] }, { "cell_type": "code", "execution_count": 32, "id": "739b43c4-c3f2-4d75-8b19-7ff91565f128", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "schema_hgs = dict(\n", " id=int,\n", " synthetic=bool,\n", " T=int,\n", " capacity=int,\n", " detextra=float,\n", " length=float,\n", " # incumbent=float,\n", " # incumbent_bound=float,\n", " exact_bound=float,\n", " # incumbent_id=int,\n", ")" ] }, { "cell_type": "code", "execution_count": 33, "id": "7003fd4f-562a-40c9-8ef1-e74c3a653759", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "data = []\n", "for rs_hgs, rs_bnc in pairs_actual + pairs_synth:\n", " data.append(dict(\n", " id=rs_hgs.id,\n", " synthetic=rs_hgs.nodes.name[0] == '!',\n", " T=rs_hgs.T,\n", " capacity=rs_hgs.capacity,\n", " detextra=rs_hgs.detextra,\n", " length=rs_hgs.length,\n", " exact_bound=rs_bnc.misc['bound'],\n", " ))\n", " # print(details['incumbent_id'], end=' ')\n", "df_hgs = pl.DataFrame(data, schema=schema_hgs)" ] }, { "cell_type": "code", "execution_count": 34, "id": "b6e39604-dc5c-4d85-8e38-ea4eb7b55fca", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "['id', 'synthetic', 'T', 'capacity', 'detextra', 'length', 'exact_bound']" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df_hgs.columns" ] }, { "cell_type": "code", "execution_count": 35, "id": "ed8caa24-665d-4fb5-9d7d-b52b310501cc", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/html": [ "
\n", "shape: (2, 2)
syntheticcount
boolu32
true6379
false732
" ], "text/plain": [ "shape: (2, 2)\n", "┌───────────┬───────┐\n", "│ synthetic ┆ count │\n", "│ --- ┆ --- │\n", "│ bool ┆ u32 │\n", "╞═══════════╪═══════╡\n", "│ true ┆ 6379 │\n", "│ false ┆ 732 │\n", "└───────────┴───────┘" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df_hgs['synthetic'].value_counts()" ] }, { "cell_type": "code", "execution_count": 36, "id": "1e16ea87-2096-4b37-b0f6-c66939701ec2", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/html": [ "
\n", "shape: (9, 2)
statisticvalue
strf64
"count"5129.0
"null_count"1982.0
"mean"0.003079
"std"0.005495
"min"-0.018452
"25%"0.000774
"50%"0.001801
"75%"0.003515
"max"0.118956
" ], "text/plain": [ "shape: (9, 2)\n", "┌────────────┬───────────┐\n", "│ statistic ┆ value │\n", "│ --- ┆ --- │\n", "│ str ┆ f64 │\n", "╞════════════╪═══════════╡\n", "│ count ┆ 5129.0 │\n", "│ null_count ┆ 1982.0 │\n", "│ mean ┆ 0.003079 │\n", "│ std ┆ 0.005495 │\n", "│ min ┆ -0.018452 │\n", "│ 25% ┆ 0.000774 │\n", "│ 50% ┆ 0.001801 │\n", "│ 75% ┆ 0.003515 │\n", "│ max ┆ 0.118956 │\n", "└────────────┴───────────┘" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df_hgs['detextra'].describe()" ] }, { "cell_type": "code", "execution_count": 37, "id": "1ba4edfb-d327-4fc3-8b4e-fbaf7676671a", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "detextra_hgs = np.sort(np.nan_to_num(np.clip(df_hgs['detextra'], 0., None), nan=0.))" ] }, { "cell_type": "code", "execution_count": 38, "id": "6e7e2b6c-dd22-41ab-8a22-f1e3040f7cc1", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/html": [ "
\n", "shape: (35, 7)
idsyntheticTcapacitydetextralengthexact_bound
i64booli64i64f64f64f64
21006false6010-0.00297551296.54665449611.477292
21209false552-0.003444182175.265645182804.81475
21208false554-0.00126699909.59356299531.718807
21556false1192-0.017189405793.043417412587.411775
21557false1193-0.007867291621.821448292531.694887
…………………
16186true7010-0.0097457.9832397.73576
16857true504-0.0038968.1061498.051141
17139true13310-0.00233312.25593211.63741
17696true688-0.0127238.9163698.541159
17764true574-0.00181610.97929510.874424
" ], "text/plain": [ "shape: (35, 7)\n", "┌───────┬───────────┬─────┬──────────┬───────────┬───────────────┬───────────────┐\n", "│ id ┆ synthetic ┆ T ┆ capacity ┆ detextra ┆ length ┆ exact_bound │\n", "│ --- ┆ --- ┆ --- ┆ --- ┆ --- ┆ --- ┆ --- │\n", "│ i64 ┆ bool ┆ i64 ┆ i64 ┆ f64 ┆ f64 ┆ f64 │\n", "╞═══════╪═══════════╪═════╪══════════╪═══════════╪═══════════════╪═══════════════╡\n", "│ 21006 ┆ false ┆ 60 ┆ 10 ┆ -0.002975 ┆ 51296.546654 ┆ 49611.477292 │\n", "│ 21209 ┆ false ┆ 55 ┆ 2 ┆ -0.003444 ┆ 182175.265645 ┆ 182804.81475 │\n", "│ 21208 ┆ false ┆ 55 ┆ 4 ┆ -0.001266 ┆ 99909.593562 ┆ 99531.718807 │\n", "│ 21556 ┆ false ┆ 119 ┆ 2 ┆ -0.017189 ┆ 405793.043417 ┆ 412587.411775 │\n", "│ 21557 ┆ false ┆ 119 ┆ 3 ┆ -0.007867 ┆ 291621.821448 ┆ 292531.694887 │\n", "│ … ┆ … ┆ … ┆ … ┆ … ┆ … ┆ … │\n", "│ 16186 ┆ true ┆ 70 ┆ 10 ┆ -0.009745 ┆ 7.983239 ┆ 7.73576 │\n", "│ 16857 ┆ true ┆ 50 ┆ 4 ┆ -0.003896 ┆ 8.106149 ┆ 8.051141 │\n", "│ 17139 ┆ true ┆ 133 ┆ 10 ┆ -0.002333 ┆ 12.255932 ┆ 11.63741 │\n", "│ 17696 ┆ true ┆ 68 ┆ 8 ┆ -0.012723 ┆ 8.916369 ┆ 8.541159 │\n", "│ 17764 ┆ true ┆ 57 ┆ 4 ┆ -0.001816 ┆ 10.979295 ┆ 10.874424 │\n", "└───────┴───────────┴─────┴──────────┴───────────┴───────────────┴───────────────┘" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Negative detextra in hgs is OK.\n", "# It means some subtree roots chosen by PathFinder were closer to root\n", "# than the path's head (since PathFinder relaxes the path-subtree constraint)\n", "df_hgs.filter(pl.col('detextra') < -1e-3)" ] }, { "cell_type": "markdown", "id": "5ce0b00a-dfbf-4b49-a497-33141c95396a", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "## B&C solver" ] }, { "cell_type": "markdown", "id": "6c1f0297-face-4a79-8613-193998e4370d", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "### Make DataFrame" ] }, { "cell_type": "code", "execution_count": 39, "id": "e413b863-9613-47f9-a0ee-dd436966f4ee", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "schema_exact = dict(\n", " id=int,\n", " synthetic=bool,\n", " T=int,\n", " capacity=int,\n", " detextra=float,\n", " length=float,\n", " bound=float,\n", ")" ] }, { "cell_type": "code", "execution_count": 40, "id": "14c6f0bc-4814-48fc-b4b9-49f89250ebd0", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "data = []\n", "for rs_hgs, rs_bnc in pairs_actual + pairs_synth:\n", " data.append(dict(\n", " id=rs_bnc.id,\n", " synthetic=rs_bnc.nodes.name[0] == '!',\n", " T=rs_bnc.T,\n", " capacity=rs_bnc.capacity,\n", " detextra=rs_bnc.detextra,\n", " length=rs_bnc.length,\n", " bound=rs_bnc.misc['bound'],\n", " ))\n", "df_BnC = pl.DataFrame(data, schema=schema_exact)" ] }, { "cell_type": "code", "execution_count": 41, "id": "05cb9c29-589a-4e1b-aa6f-333124085420", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "7111" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df_BnC.height" ] }, { "cell_type": "code", "execution_count": 42, "id": "879d05d5-680f-4475-ab0b-f85744aa5be1", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/html": [ "
\n", "shape: (9, 2)
statisticvalue
strf64
"count"4949.0
"null_count"2162.0
"mean"0.002359
"std"0.004466
"min"-0.009212
"25%"0.000637
"50%"0.001591
"75%"0.003006
"max"0.122635
" ], "text/plain": [ "shape: (9, 2)\n", "┌────────────┬───────────┐\n", "│ statistic ┆ value │\n", "│ --- ┆ --- │\n", "│ str ┆ f64 │\n", "╞════════════╪═══════════╡\n", "│ count ┆ 4949.0 │\n", "│ null_count ┆ 2162.0 │\n", "│ mean ┆ 0.002359 │\n", "│ std ┆ 0.004466 │\n", "│ min ┆ -0.009212 │\n", "│ 25% ┆ 0.000637 │\n", "│ 50% ┆ 0.001591 │\n", "│ 75% ┆ 0.003006 │\n", "│ max ┆ 0.122635 │\n", "└────────────┴───────────┘" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df_BnC['detextra'].describe()" ] }, { "cell_type": "code", "execution_count": 43, "id": "99f2ed83-1170-4a9f-883f-68bbc4b86b00", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "detextra_BnC = np.sort(np.nan_to_num(np.clip(df_BnC['detextra'], 0., None), nan=0.))" ] }, { "cell_type": "markdown", "id": "38ef0a61-7066-41ba-9abe-43460e4ae2ec", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "## 3.3 Impact of detours on the solver's total length" ] }, { "cell_type": "code", "execution_count": 44, "id": "e809ae10-4e45-4146-bf57-45acb0182f90", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", " \n", " image/svg+xml\n", " \n", " \n", " OptiWindNet\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 3100\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 3200\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.0\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.5\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 1.0\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 1.5\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 2.0\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 2.5\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 3.0\n", " \n", " \n", " \n", " Relative increase (%)\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 200\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 400\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 600\n", " \n", " \n", " \n", " Count\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " B&C instances: 7111\n", " \n", " \n", " \n", " \n", " \n", " Instance count\n", " \n", " \n", " \n", " \n", " \n", " ≤ 2%: 99.8%\n", " \n", " \n", " \n", " \n", " \n", " ≤ 1%: 98.8%\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": [ "with plt.style.context(pub_style):\n", " data = 100*detextra_BnC\n", "\n", " fig, (ax1, ax2) = plt.subplots(2, 1, height_ratios=[1, 5], figsize=(3.5, 2),\n", " facecolor='w', sharex=True)\n", " # fig.subplots_adjust(hspace=0.05)\n", " ax1.spines.bottom.set_visible(False)\n", " ax1.xaxis.tick_top()\n", " ax1.tick_params(labeltop=False)\n", " num_data = len(data)\n", " below1 = data <= 1\n", " below2 = data <= 2\n", " bins = np.linspace(0, 3, num=76)\n", " # bins = None\n", "\n", " # top y_axis segment\n", " H1, X1, art1_ = ax1.hist(data[below1], bins = bins, color='tab:blue',\n", " histtype='stepfilled', alpha=0.3)\n", " H2, X2, art2_ = ax1.hist(data[below2], bins = bins, edgecolor='tab:blue',\n", " histtype='stepfilled', hatch=r'\\\\\\\\', facecolor='none')\n", " H, X, art_ = ax1.hist(data, bins = bins, color='tab:blue', histtype='step')\n", "\n", " # main y_axis segment\n", " H1, X1, art1_ = ax2.hist(data[below1], bins = bins, color='tab:blue',\n", " histtype='stepfilled', alpha=0.3)\n", " H2, X2, art2_ = ax2.hist(data[below2], bins = bins, edgecolor='tab:blue',\n", " histtype='stepfilled', hatch=r'\\\\\\\\', facecolor='none')\n", " H, X, art_ = ax2.hist(data, bins = bins, color='tab:blue', histtype='step')\n", "\n", " ax1.set_ylim(3100, 3200) # outliers only\n", " ax2.set_ylim(0, 600) # most of the data\n", "\n", " C1, C2 = H1.sum(), H2.sum()\n", " leg = ax2.legend( # the empty Line2D is a hack to get a line instead of a patch\n", " [Line2D([], []), art2_[0], art1_[0]],\n", " ['Instance count',\n", " f'≤ 2%: {100*C2/num_data:.1f}%',\n", " f'≤ 1%: {100*C1/num_data:.1f}%'],\n", " title=f'B&C instances: {num_data}'\n", " )\n", " ax2.set_ylabel('Count')\n", " ax2.set_xlabel('Relative increase (%)')\n", " leg.legend_handles[0] = Line2D([], [])\n", " ax1.figure.savefig('fig_detextra_BnC.pdf', transparent=False)\n", " pass" ] }, { "cell_type": "code", "execution_count": 45, "id": "8ae42abf-ac77-44fa-bfb4-2d8b11e33388", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", " \n", " image/svg+xml\n", " \n", " \n", " OptiWindNet\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 2800\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 2900\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.0\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0.5\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 1.0\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 1.5\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 2.0\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 2.5\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 3.0\n", " \n", " \n", " \n", " Relative increase (%)\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 200\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 400\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 600\n", " \n", " \n", " \n", " Count\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " HGS instances: 7111\n", " \n", " \n", " \n", " \n", " \n", " Instance count\n", " \n", " \n", " \n", " \n", " \n", " ≤ 2%: 99.1%\n", " \n", " \n", " \n", " \n", " \n", " ≤ 1%: 96.5%\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": [ "with plt.style.context(pub_style):\n", "# with plt.style.context('pub_paperfarm'):\n", "# if True:\n", " data = 100*detextra_hgs\n", "\n", " fig, (ax1, ax2) = plt.subplots(2, 1, height_ratios=[1, 5], figsize=(3.5, 2),\n", " facecolor='w', sharex=True)\n", " # fig.subplots_adjust(hspace=0.05)\n", " ax1.spines.bottom.set_visible(False)\n", " ax1.xaxis.tick_top()\n", " ax1.tick_params(labeltop=False)\n", " num_data = len(data)\n", " below1 = data <= 1\n", " below2 = data <= 2\n", " bins = np.linspace(0, 3, num=76)\n", " # bins = None\n", "\n", " # top y_axis segment\n", " H1, X1, art1_ = ax1.hist(data[below1], bins = bins, color='tab:blue',\n", " histtype='stepfilled', alpha=0.3)\n", " H2, X2, art2_ = ax1.hist(data[below2], bins = bins, edgecolor='tab:blue',\n", " histtype='stepfilled', hatch=r'\\\\\\\\', facecolor='none')\n", " H, X, art_ = ax1.hist(data, bins = bins, color='tab:blue', histtype='step')\n", "\n", " # main y_axis segment\n", " H1, X1, art1_ = ax2.hist(data[below1], bins = bins, color='tab:blue',\n", " histtype='stepfilled', alpha=0.3)\n", " H2, X2, art2_ = ax2.hist(data[below2], bins = bins, edgecolor='tab:blue',\n", " histtype='stepfilled', hatch=r'\\\\\\\\', facecolor='none')\n", " H, X, art_ = ax2.hist(data, bins = bins, color='tab:blue', histtype='step')\n", "\n", " ax1.set_ylim(2800, 2900) # outliers only\n", " ax2.set_ylim(0, 600) # most of the data\n", "\n", " C1, C2 = H1.sum(), H2.sum()\n", " leg = ax2.legend( # the empty Line2D is a hack to get a line instead of a patch\n", " [Line2D([], []), art2_[0], art1_[0]],\n", " ['Instance count',\n", " f'≤ 2%: {100*C2/num_data:.1f}%',\n", " f'≤ 1%: {100*C1/num_data:.1f}%'],\n", " title=f'HGS instances: {num_data}'\n", " )\n", " ax2.set_ylabel('Count')\n", " ax2.set_xlabel('Relative increase (%)')\n", " leg.legend_handles[0] = Line2D([], [])\n", " ax1.figure.savefig('fig_detextra_HGS.pdf', transparent=False)\n", " pass" ] }, { "cell_type": "markdown", "id": "dbb568ee-e256-4dae-9b49-72ab5dc8bd76", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "## 3.4 Comparison of B&C and HGS solutions" ] }, { "cell_type": "code", "execution_count": 46, "id": "9a8924da-275a-4928-b3aa-916078346604", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", " \n", " \n", " \n", " \n", " image/svg+xml\n", " \n", " \n", " OptiWindNet\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " −2\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 2\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 4\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 6\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 8\n", " \n", " \n", " \n", " Relative difference (%)\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 0\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 250\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 500\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 750\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " 1000\n", " \n", " \n", " \n", " Count\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " Instances: 7111\n", " \n", " \n", " \n", " \n", " \n", " HGS to B&C gap\n", " \n", " \n", " \n", " \n", " \n", " ≤ 2%: 80.4%\n", " \n", " \n", " \n", " \n", " \n", " ≤ 1%: 60.6%\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": [ "with plt.style.context(pub_style):\n", " data_HGSvsBnC_gap = 1 - df_BnC['length']/df_hgs['length']\n", " data = 100*data_HGSvsBnC_gap.to_numpy()\n", "\n", " fig, ax = plt.subplots(facecolor='w', figsize=(3.5, 2))\n", " num_data = len(data)\n", " below1 = data <= 1\n", " below2 = data <= 2\n", " elsewhere = data > 2\n", " bins = np.linspace(-2, 8, num=201)\n", "\n", " # main y_axis segment\n", " H1, X1, art1_ = ax.hist(data[below1], bins = bins, color='tab:blue',\n", " histtype='stepfilled', alpha=0.3)\n", " H2, X2, art2_ = ax.hist(data[below2], bins = bins, edgecolor='tab:blue',\n", " histtype='stepfilled', hatch=r'\\\\\\\\', facecolor='none')\n", " H, X, art_ = ax.hist(data, bins = bins, color='tab:blue', histtype='step')\n", "\n", " C1, C2 = H1.sum(), H2.sum()\n", " leg = ax.legend( # the empty Line2D is a hack to get a line instead of a patch\n", " [Line2D([], []), art2_[0], art1_[0]],\n", " ['HGS to B&C gap',\n", " f'≤ 2%: {100*C2/num_data:.1f}%',\n", " f'≤ 1%: {100*C1/num_data:.1f}%'],\n", " title=f'Instances: {num_data}'\n", " )\n", " ax.set_ylabel('Count')\n", " ax.set_xlabel('Relative difference (%)')\n", " leg.legend_handles[0] = Line2D([], [])\n", " ax.set_xlim(-2, 8)\n", " ax.figure.savefig('fig_HGS_to_BnC_gap.pdf', transparent=False)\n", " pass" ] }, { "cell_type": "markdown", "id": "1aaf684c-ab65-424c-a830-b15c5e65cfa2", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "## 3.5 Dealing with crossings from HGS-CVRP" ] }, { "cell_type": "markdown", "id": "dd178c05-d70c-4dd8-bd11-27ac3a342029", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "### Select HGS-CVRP entries" ] }, { "cell_type": "code", "execution_count": 47, "id": "610fa136-bf93-4dca-8f97-061e3056bd87", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "7111" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df_hgs.height" ] }, { "cell_type": "code", "execution_count": 48, "id": "6937be9d-c781-4ff0-a1ef-fe23a683f867", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [], "source": [ "method_hgs = Method.select().where(\n", " Method.funname == 'hgs_cvrp',\n", " Method.options['timeLimit'] == 120\n", ")" ] }, { "cell_type": "code", "execution_count": 49, "id": "f70a0e56-345d-4981-b6a1-3e27fcbb9229", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "method_hgs.count()" ] }, { "cell_type": "code", "execution_count": 50, "id": "7befe798-0a45-49a9-b9f9-3b19611ffcc7", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "7044" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hgs_all = RouteSet.select().where(\n", " RouteSet.method.in_([m.digest for m in method_hgs])\n", ")\n", "hgs_all.count()" ] }, { "cell_type": "code", "execution_count": 51, "id": "8e480d1a-e19a-4779-8697-c73738542c95", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hgs_invalid = 0 # routeset.valid removed from the schema\n", "hgs_invalid" ] }, { "cell_type": "code", "execution_count": 52, "id": "27591fc6-9636-4f91-9902-681aaabc9813", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "332" ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# just the instances repaired after the first hgs run\n", "hgs_repaired = hgs_all.where(\n", " RouteSet.misc['repaired'].is_null(False),\n", " RouteSet.misc['hgs_reruns'].is_null(),\n", ")\n", "hgs_repaired.count()" ] }, { "cell_type": "code", "execution_count": 53, "id": "87d4e1e3-be42-496c-a105-d5750aebcfb5", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "98" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hgs_reruns = hgs_all.where(\n", " RouteSet.misc['hgs_reruns'].is_null(False),\n", ")\n", "hgs_reruns.count()" ] }, { "cell_type": "markdown", "id": "ee82f4bc-17d1-41c6-8d22-a316f0ded613", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "### Statistics" ] }, { "cell_type": "code", "execution_count": 54, "id": "8783bbd5-e594-44c5-ac84-4e29d9f55dce", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "7111" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hgs_all = RouteSet.select().where(\n", " RouteSet.creator == 'baselines.hgs'\n", ")\n", "hgs_all.count()" ] }, { "cell_type": "code", "execution_count": 55, "id": "9debb24a-9a26-4c09-b61f-2aa878f81c3c", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "332" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# just the instances repaired after the first hgs run\n", "hgs_repaired = hgs_all.where(\n", " RouteSet.misc['repaired'].is_null(False),\n", " RouteSet.misc['hgs_reruns'].is_null(),\n", ")\n", "hgs_repaired.count()" ] }, { "cell_type": "code", "execution_count": 56, "id": "7c54f498-e563-4467-b61d-987263e391b1", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "98" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hgs_reruns = hgs_all.where(\n", " RouteSet.misc['hgs_reruns'].is_null(False),\n", ")\n", "hgs_reruns.count()" ] }, { "cell_type": "code", "execution_count": 57, "id": "8352290c-aae6-488b-8643-c2bf7e5574af", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "0.06046969483898186" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(hgs_repaired.count() + hgs_reruns.count())/hgs_all.count()" ] }, { "cell_type": "code", "execution_count": 58, "id": "f921980f-4539-474a-a2fc-77e558cf554d", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "0.04668822950358599" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hgs_repaired.count()/hgs_all.count()" ] }, { "cell_type": "code", "execution_count": 59, "id": "88244c56-235c-48f9-a181-98fd2d2647ee", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "data": { "text/plain": [ "0.013781465335395865" ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "hgs_reruns.count()/hgs_all.count()" ] }, { "cell_type": "markdown", "id": "2e9b347e-5f50-4dcc-8a54-118163da71db", "metadata": { "deletable": true, "editable": true, "frozen": false }, "source": [ "### Examining re-runs" ] }, { "cell_type": "code", "execution_count": 60, "id": "d25ed1e4-9738-4679-9e8d-b74faac7f6b1", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 81 0.011390802981296582\n", "2 12 0.0016875263675994938\n", "3 2 0.0002812543945999156\n", "4 1 0.0001406271972999578\n", "5 2 0.0002812543945999156\n", "6 0 0.0\n", "7 0 0.0\n", "8 0 0.0\n", "9 0 0.0\n" ] } ], "source": [ "subcounts = []\n", "for reruns in range(1, 10):\n", " count = hgs_reruns.where(\n", " RouteSet.misc['hgs_reruns'] == reruns\n", " ).count()\n", " subcounts.append(count)\n", " print(reruns, count, count/hgs_all.count())" ] }, { "cell_type": "code", "execution_count": 61, "id": "61957192-12c4-4f59-b72b-7bea0bbb0827", "metadata": { "deletable": true, "editable": true, "frozen": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 82.7%\n", "2 12.2%\n", "3 2.0%\n", "4 1.0%\n", "5 2.0%\n", "6 0.0%\n", "7 0.0%\n", "8 0.0%\n", "9 0.0%\n" ] } ], "source": [ "total = sum(subcounts)\n", "for reruns, count in zip(range(1, 10), subcounts):\n", " print(reruns, f'{100*count/total:.1f}%')" ] } ], "metadata": { "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 5 }