authors/mapgccv/miscellaneous/Dynamic_routing_example.ipynb

{
  "cells": [
    {
      "attachments": {},
      "cell_type": "markdown",
      "metadata": {
        "id": "7RjB1ipC7KbS"
      },
      "source": [
        "# Dynamic routing example\n",
        "[![Dynamic_routing_example.ipynb](https://img.shields.io/badge/github-%23121011.svg?logo=github)](https://github.com/ampl/colab.ampl.com/blob/master/authors/mapgccv/miscellaneous/Dynamic_routing_example.ipynb) [![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/ampl/colab.ampl.com/blob/master/authors/mapgccv/miscellaneous/Dynamic_routing_example.ipynb) [![Kaggle](https://kaggle.com/static/images/open-in-kaggle.svg)](https://kaggle.com/kernels/welcome?src=https://github.com/ampl/colab.ampl.com/blob/master/authors/mapgccv/miscellaneous/Dynamic_routing_example.ipynb) [![Gradient](https://assets.paperspace.io/img/gradient-badge.svg)](https://console.paperspace.com/github/ampl/colab.ampl.com/blob/master/authors/mapgccv/miscellaneous/Dynamic_routing_example.ipynb) [![Open In SageMaker Studio Lab](https://studiolab.sagemaker.aws/studiolab.svg)](https://studiolab.sagemaker.aws/import/github/ampl/colab.ampl.com/blob/master/authors/mapgccv/miscellaneous/Dynamic_routing_example.ipynb) [![Hits](https://h.ampl.com/https://github.com/ampl/colab.ampl.com/blob/master/authors/mapgccv/miscellaneous/Dynamic_routing_example.ipynb)](https://colab.ampl.com)\n",
        "\n",
        "Description: Example of interactive optimization with GUI using AMPL and Google Maps\n",
        "\n",
        "Tags: amplpy,gui\n",
        "\n",
        "Notebook author: Christian Valente <<christian.valente@gmail.com>>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 13,
      "metadata": {
        "id": "rQ50dBwL7KbX"
      },
      "outputs": [],
      "source": [
        "# Install dependencies\n",
        "%pip install -q amplpy pandas"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 14,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "s7DEaRp87KbY",
        "outputId": "f41f64ae-0e30-4949-f3b1-0e69d8eaa38e"
      },
      "outputs": [],
      "source": [
        "# Google Colab & Kaggle integration\n",
        "from amplpy import AMPL, ampl_notebook\n",
        "\n",
        "ampl = ampl_notebook(\n",
        "    modules=[\"highs\"],  # modules to install\n",
        "    license_uuid=\"default\",  # license to use\n",
        ")  # instantiate AMPL object and register magics"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oZ1BTFLaLNEb"
      },
      "source": [
        "## Introduction\n",
        "This example shows how to create a simple GUI for a routing problem that allows to:\n",
        "\n",
        "* visualize inputs and solutions on a map\n",
        "* dynamically add points by clicking on the map itself\n",
        "* show each step of the row generation methodology applied to solve it"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FRDegAYbzPek"
      },
      "source": [
        "### Insert your Google Maps API key\n",
        "Follow [the instructions](https://jupyter-gmaps.readthedocs.io/en/latest/authentication.html) to generate a Google Maps key for development, then insert it in the placeholder below."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 15,
      "metadata": {
        "id": "_V3Ql6EWzQOC"
      },
      "outputs": [],
      "source": [
        "API_KEY = \"\"  # Fill in with your API key"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "95wjAiaJUaMY"
      },
      "source": [
        "## Install and import dependencies\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "_LtwWnK2UYYq"
      },
      "outputs": [],
      "source": [
        "if not API_KEY:\n",
        "    raise ValueError(\"Please insert your Google maps API key\")\n",
        "%pip install -q gmaps\n",
        "import gmaps\n",
        "\n",
        "gmaps.configure(api_key=API_KEY)\n",
        "# Activate custom widgets manager\n",
        "from google.colab import output\n",
        "\n",
        "output.enable_custom_widget_manager()\n",
        "# Import display and ipywidgets\n",
        "from IPython.display import display\n",
        "import ipywidgets as widgets\n",
        "\n",
        "# Import needed data/maths libs\n",
        "import pandas as pd\n",
        "import math\n",
        "import collections\n",
        "import sys\n",
        "\n",
        "# collections.Iterable after python 3.9\n",
        "if sys.version_info >= (3, 10):\n",
        "    collections.Iterable = collections.abc.Iterable"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jCyp8qRS7Kba"
      },
      "source": [
        "## Google Maps related helper class\n",
        "This class wraps all the implementation details related to graphically rendering the map and creating the buttons and textboxes that form the graphical interface you'll see at the bottom.\n",
        "\n",
        "It has to be initialized passing a callback that will be executed when the button *Solve* is clicked.\n",
        "It also has functions to programmatically add markers to the map, to retrieve the markers location (both the ones added programmatically and the ones added by simply clicking on the map) and to draw lines on the map itself."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "jYDiBDD_7Kba"
      },
      "outputs": [],
      "source": [
        "class MyMap:\n",
        "    def __init__(self, solve_function):\n",
        "        # Create the google maps widget\n",
        "        self._figure = gmaps.figure(\n",
        "            layout={\n",
        "                \"width\": \"1200px\",\n",
        "                \"height\": \"800px\",\n",
        "                \"border\": \"1px solid black\",\n",
        "                \"padding\": \"1px\",\n",
        "            }\n",
        "        )\n",
        "        # Add a marker layer, used to programmatically display markers\n",
        "        self._markers = gmaps.marker_layer([])\n",
        "        # Add a drawing layer, used to catch user interactions (additional markers)\n",
        "        # and to draw the lines on the map\n",
        "        self._drawing = gmaps.drawing_layer(show_controls=False)\n",
        "        self._drawing.on_new_feature(self._new_feature_callback)\n",
        "        self._figure.add_layer(self._drawing)\n",
        "        # Register a handler to call when the solve button is cliecked\n",
        "        self._solve_function = solve_function\n",
        "\n",
        "        # Create a textbox and two buttons\n",
        "        self._infoBox = widgets.Text(\n",
        "            description=\"Status\",\n",
        "            disabled=True,\n",
        "            layout={\"width\": \"85%\", \"margin\": \"10px 0 0 0\"},\n",
        "        )\n",
        "        self._btn_clear = widgets.Button(\n",
        "            description=\"Clean\",\n",
        "            disabled=False,\n",
        "            button_style=\"success\",\n",
        "            tooltip=\"Clear map\",\n",
        "            icon=\"redo\",\n",
        "        )\n",
        "        self._btn_solve = widgets.Button(\n",
        "            description=\"Solve\",\n",
        "            disabled=False,\n",
        "            button_style=\"success\",\n",
        "            tooltip=\"Solve model\",\n",
        "            icon=\"bolt\",\n",
        "        )\n",
        "\n",
        "        self._btn_clear.on_click(self.clear_click)\n",
        "        self._btn_solve.on_click(self.solve_click)\n",
        "        self._hcontainer = widgets.HBox([self._btn_clear, self._btn_solve])\n",
        "        self._container = widgets.VBox([self._figure, self._infoBox, self._hcontainer])\n",
        "\n",
        "        self.set_solving_status(\"init\")\n",
        "\n",
        "    def add_points(self, coordinates: list):\n",
        "        # Programmatically add markers to the map\n",
        "        markers = [gmaps.Marker(location=c) for c in coordinates]\n",
        "        self._markers.markers = markers\n",
        "        self._figure.add_layer(self._markers)\n",
        "\n",
        "    def get_points(self) -> list:\n",
        "        # Get the points on the map (both added programmatically and drawn by the user)\n",
        "        additionalPoints = [\n",
        "            f for f in self._drawing.features if isinstance(f, gmaps.Marker)\n",
        "        ]\n",
        "        return [m.location for m in self._markers.markers + additionalPoints]\n",
        "\n",
        "    def clean(self, markers=True, lines=True):\n",
        "        # Clean the map of markers and/or lines\n",
        "        if markers:\n",
        "            self._markers.markers = []\n",
        "            self._drawing.features = [\n",
        "                f for f in self._drawing.features if not isinstance(f, gmaps.Marker)\n",
        "            ]\n",
        "        if lines:\n",
        "            self._drawing.features = [\n",
        "                f for f in self._drawing.features if isinstance(f, gmaps.Marker)\n",
        "            ]\n",
        "\n",
        "    def solve_click(self, obj):\n",
        "        # Event handler for button click, execute the callback\n",
        "        self._solve_function(self, self._status == \"solving\")\n",
        "\n",
        "    def _new_feature_callback(self, feature):\n",
        "        # when a new marker is added to the map, invalidate the previous path,\n",
        "        # when a line is added, do nothing\n",
        "        if isinstance(feature, gmaps.Line):\n",
        "            return\n",
        "        if self._status != \"init\":\n",
        "            self.log(\"Location added, solution interrupted\")\n",
        "            self.set_solving_status(\"init\")\n",
        "            self.clean(markers=False)\n",
        "\n",
        "    def clear_click(self, obj):\n",
        "        # Event handler for clean button click, clear the map\n",
        "        self.clean()\n",
        "        self.log(\"Reset map\")\n",
        "        self.set_solving_status(\"init\")\n",
        "\n",
        "    def __draw_route(self, start: tuple, end: tuple):\n",
        "        # Draw a single line on the map\n",
        "        return gmaps.Line(start=start, end=end, stroke_weight=4.0, stroke_color=\"black\")\n",
        "\n",
        "    def add_arcs(self, arcs: list):\n",
        "        # Add the list of arcs (expressed as a list of tuples of coordinates,\n",
        "        # e.g. [((startLat1, startLong1), (endLat1, endLong1)),\n",
        "        #       ((startLat2, startLong2), (endLat2, endLong2)), ...]\n",
        "        lines = self._drawing.features.copy()\n",
        "        for start, end in arcs:\n",
        "            lines.append(self.__draw_route(start, end))\n",
        "        self._drawing.features = lines\n",
        "\n",
        "    def set_solving_status(self, status: str):\n",
        "        # Set the solving status (affects the buttons on the GUI)\n",
        "        # valid values: init|solving|finished\n",
        "        self._status = status\n",
        "        self._btn_solve.description = (\n",
        "            \"Solve\" if status != \"solving\" else \"Continue solving\"\n",
        "        )\n",
        "        self._btn_solve.disabled = status == \"finished\"\n",
        "\n",
        "    def log(self, text):\n",
        "        # set the message box to the specified text\n",
        "        self._infoBox.value = text\n",
        "\n",
        "    def render(self):\n",
        "        # Render the map and its container\n",
        "        return self._container"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "twrd0pLo7KbZ"
      },
      "source": [
        "## AMPL model: *TSP model with subtour elimination*\n",
        "\n",
        "The standard integer programming formulation of the Travelling Salesman Problem is as follows:\n",
        "\n",
        "Given a set of cities $S=\\{1,..,n\\}$ and distances $c_{ij}$ ($i,j \\in S$), we define:\n",
        "\n",
        "* $x_{ij} \\in \\{0,1\\}  \\forall i \\in S, j \\in S, i \\ne j $ a variable denoting if path from $i$ to $j$ or from $j$ to $i$ is part of ours solution.\n",
        "\n",
        "Our aim is to minimize the total tour length:\n",
        "\n",
        "* $\\sum_{i=1}^{n} \\sum_{j=1,j \\neq i}^{n} c_{ij}x{ij}$ \n",
        "\n",
        "while visiting all cities once, which is enforced with these two constraints:\n",
        "\n",
        "* $\\sum_{i=1,i \\neq j} x_{ij} \\forall j \\in S$\n",
        "\n",
        "and\n",
        "\n",
        "* $\\sum_{j=1,j \\neq i} x_{ij} \\forall i \\in S$\n",
        "\n",
        "This formulation notably allows for subtours that can be eliminated with a suitable *subtour-elimination* constraint; the number of possible subtours grows exponentially with the number of cities, so one approach is to eliminate only the subtours that result from actually obtained solutions.\n",
        "\n",
        "The following AMPL model expresses the problem above with a slight semplification: we suppose the distance/cost matrix is symmetrical (aka the distances between each pair of cities is the same both ways), so we can consider only half the possible pairs for $X$. So we define:\n",
        "\n",
        "*  $x_{ij} \\in \\{0,1\\}  \\forall i \\in S, j \\in S, i > j $\n",
        "\n",
        "and we change the formulation accordingly."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "aEtyesqs7KbZ"
      },
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "# List of nodes\n",
        "set NODES ordered;\n",
        "# Longitude and latitude of each node; not used in the model,\n",
        "# just for data retrieval\n",
        "param longitude {NODES};\n",
        "param latitude {NODES};\n",
        "# Set of valid city pairs (segments)\n",
        "set PAIRS := {i in NODES, j in NODES: ord(i) < ord(j)};\n",
        "# Distance of each valid route\n",
        "param distance {(i,j) in PAIRS};\n",
        "\n",
        "# If set to 1, the relative segment is part of the solution\n",
        "var X{PAIRS} binary;\n",
        "# Minimize the total tour length\n",
        "minimize Tour_Length: sum {(i,j) in PAIRS} distance[i,j] * X[i,j];\n",
        "\n",
        "# Each node must have two segments active, showing that we get in\n",
        "# and out of it\n",
        "subject to Visit_All {i in NODES}:\n",
        "   sum {(i, j) in PAIRS} X[i,j] + sum {(j, i) in PAIRS} X[j,i] = 2;\n",
        "\n",
        "# The following are used in the subtour elimination procedure\n",
        "param nSubtours >= 0 integer, default 0;\n",
        "set SUB {1..nSubtours} within NODES;\n",
        "# Subtour elimination constraint\n",
        "# For each stored subtour, make sure that there is at least one segment\n",
        "# leading into the subtour itself (so that it is not a subtour any longer)\n",
        "subject to Subtour_Elimination {k in 1..nSubtours}:\n",
        "  sum {i in SUB[k], j in NODES diff SUB[k]} \n",
        "      if (i, j) in PAIRS then X[i, j] else X[j, i] >= 2;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5iSMYR18JyHW"
      },
      "source": [
        "### Model-related functions\n",
        "For convenience in getting data from the underlying `AMPL` object, we addd the following methods to the class itself. \n",
        "These can then be called via normal members function syntax, e.g. `ampl.function_name()`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "usnxYnu3K9Mu"
      },
      "outputs": [],
      "source": [
        "def get_arcs(self) -> list:\n",
        "    return [\n",
        "        (i, j)\n",
        "        for (i, j, k) in self.get_data(\n",
        "            \"{(i,j) in PAIRS : X[i,j] > 0} X[i,j];\"\n",
        "        ).to_list()\n",
        "    ]\n",
        "\n",
        "\n",
        "AMPL.get_arcs = get_arcs\n",
        "\n",
        "\n",
        "def get_coords(self) -> dict:\n",
        "    return self.get_data(\"latitude, longitude\").to_dict()\n",
        "\n",
        "\n",
        "AMPL.get_coords = get_coords\n",
        "\n",
        "\n",
        "def get_nodes(self) -> set:\n",
        "    return set(self.get_set(\"NODES\").members())\n",
        "\n",
        "\n",
        "AMPL.get_nodes = get_nodes"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ckyHrxstUCkT"
      },
      "source": [
        "### Subtour-related helper functions\n",
        "These functions identify subtours from a list of arcs. Note that we could have also dynamically added to the AMPL object, we have chosen not-to to show both approaches."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "IAgxvoWVT5K0"
      },
      "outputs": [],
      "source": [
        "import math\n",
        "from itertools import tee\n",
        "\n",
        "\n",
        "# Graphs helper routines\n",
        "def trasverse(node, arcs: list, allnodes: set, subtour=None) -> list:\n",
        "    # Trasverses all the arcs in the set arcs, starting from node\n",
        "    # and returns the tour\n",
        "    if not subtour:\n",
        "        subtour = list()\n",
        "    # Find arcs involving the current node\n",
        "    myarcs = [(i, j) for (i, j) in arcs if node == i or node == j]\n",
        "    if len(myarcs) == 0:\n",
        "        return\n",
        "    # Append the current node to the current subtour\n",
        "    subtour.append(node)\n",
        "    # Use the first arc found\n",
        "    myarc = myarcs[0]\n",
        "    # Find destination (or origin) node\n",
        "    destination = next(i for i in myarc if i != node)\n",
        "    # Remove from arcs and nodes to visit\n",
        "    arcs.remove(myarc)\n",
        "    if node in allnodes:\n",
        "        allnodes.remove(node)\n",
        "\n",
        "    trasverse(destination, arcs, allnodes, subtour)\n",
        "    return subtour\n",
        "\n",
        "\n",
        "def as_steps(iterable):\n",
        "    a, b = tee(iterable)\n",
        "    next(b, None)\n",
        "    return list(zip(a, b))\n",
        "\n",
        "\n",
        "def find_subtours(arcs: list, allnodes: set):\n",
        "    # Find all the subtours defined by a set of arcs and\n",
        "    # return them as a list of list\n",
        "    subtours = list()\n",
        "    allnodes = allnodes.copy()\n",
        "    while len(allnodes) > 0:\n",
        "        l = trasverse(next(iter(allnodes)), arcs, allnodes)\n",
        "        subtours.append(l)\n",
        "    return subtours"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "60trH8W9U_I-"
      },
      "source": [
        "## Data related helpers\n",
        "Set of functions designed to provide sample data and preprocess it so that it has all the properties needed for the solution process."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "kp4VCq4SU-bc"
      },
      "outputs": [],
      "source": [
        "def haversine(coord1, coord2):\n",
        "    # Calculate distance between coordinates on Earth's surface\n",
        "    R = 6372800  # Earth radius in meters\n",
        "    lat1, lon1 = coord1\n",
        "    lat2, lon2 = coord2\n",
        "\n",
        "    phi1, phi2 = math.radians(lat1), math.radians(lat2)\n",
        "    dphi = math.radians(lat2 - lat1)\n",
        "    dlambda = math.radians(lon2 - lon1)\n",
        "\n",
        "    a = (\n",
        "        math.sin(dphi / 2) ** 2\n",
        "        + math.cos(phi1) * math.cos(phi2) * math.sin(dlambda / 2) ** 2\n",
        "    )\n",
        "\n",
        "    return 2 * R * math.atan2(math.sqrt(a), math.sqrt(1 - a))\n",
        "\n",
        "\n",
        "def define_data(coordinates: list, names: list = None) -> tuple[list, pd.DataFrame]:\n",
        "    # Get two dataframes (one with the properly coordinates, one with the distances) given a list of\n",
        "    # coordinates\n",
        "    df = pd.DataFrame.from_records(\n",
        "        coordinates, columns=[\"latitude\", \"longitude\"], index=names\n",
        "    )\n",
        "    df.index.name = \"NODE\"\n",
        "    nodes = list(df.index)\n",
        "    distances = {\n",
        "        (orig, dest): [\n",
        "            round(\n",
        "                haversine(\n",
        "                    (df.loc[orig][\"latitude\"], df.loc[orig][\"longitude\"]),\n",
        "                    (df.loc[dest][\"latitude\"], df.loc[dest][\"longitude\"]),\n",
        "                )\n",
        "                / 1000\n",
        "            )\n",
        "        ]\n",
        "        for orig in nodes\n",
        "        for dest in nodes\n",
        "        if nodes.index(dest) > nodes.index(orig)\n",
        "    }\n",
        "    return (df, distances)\n",
        "\n",
        "\n",
        "def sample_data():\n",
        "    # Get some sample data\n",
        "    otherLocs = [\n",
        "        {\n",
        "            \"name\": \"Bolzano Airport\",\n",
        "            \"city\": \"Bolzano\",\n",
        "            \"country\": \"Italy\",\n",
        "            \"iata\": \"BZO\",\n",
        "            \"latitude\": 46.4626,\n",
        "            \"longitude\": 11.3264,\n",
        "        },\n",
        "        {\n",
        "            \"name\": \"Ottawa Macdonald-Cartier International Airport\",\n",
        "            \"city\": \"Ottawa\",\n",
        "            \"country\": \"Canada\",\n",
        "            \"iata\": \"YOW\",\n",
        "            \"latitude\": 45.3208,\n",
        "            \"longitude\": -75.6724,\n",
        "        },\n",
        "        {\n",
        "            \"name\": \"Porto Airport\",\n",
        "            \"city\": \"Porto\",\n",
        "            \"country\": \"Portugal\",\n",
        "            \"iata\": \"OPO\",\n",
        "            \"latitude\": 41.2481,\n",
        "            \"longitude\": -8.681389,\n",
        "        },\n",
        "        {\n",
        "            \"name\": \"Newark Liberty International Airport\",\n",
        "            \"city\": \"Newark\",\n",
        "            \"country\": \"United States\",\n",
        "            \"iata\": \"EWR\",\n",
        "            \"latitude\": 40.6925,\n",
        "            \"longitude\": -74.168611,\n",
        "        },\n",
        "        {\n",
        "            \"name\": \"Madrid Barajas Airport\",\n",
        "            \"city\": \"Madrid\",\n",
        "            \"country\": \"Spain\",\n",
        "            \"iata\": \"MAD\",\n",
        "            \"latitude\": 40.493556,\n",
        "            \"longitude\": -3.566764,\n",
        "        },\n",
        "        {\n",
        "            \"name\": \"Chicago O'Hare International Airport\",\n",
        "            \"city\": \"Chicago\",\n",
        "            \"country\": \"United States\",\n",
        "            \"iata\": \"ORD\",\n",
        "            \"latitude\": 41.978611,\n",
        "            \"longitude\": -87.904722,\n",
        "        },\n",
        "        {\n",
        "            \"name\": \"Albuquerque International Sunport\",\n",
        "            \"city\": \"Albuquerque\",\n",
        "            \"country\": \"United States\",\n",
        "            \"iata\": \"ABQ\",\n",
        "            \"latitude\": 35.0401,\n",
        "            \"longitude\": -106.6094,\n",
        "        },\n",
        "        {\n",
        "            \"name\": \"Melbourne Airport\",\n",
        "            \"city\": \"Melbourne\",\n",
        "            \"country\": \"Australia\",\n",
        "            \"iata\": \"MEL\",\n",
        "            \"latitude\": -37.673333,\n",
        "            \"longitude\": 144.843333,\n",
        "        },\n",
        "        {\n",
        "            \"name\": \"San Francisco International Airport\",\n",
        "            \"city\": \"San Francisco\",\n",
        "            \"country\": \"United States\",\n",
        "            \"iata\": \"SFO\",\n",
        "            \"latitude\": 37.618889,\n",
        "            \"longitude\": -122.375,\n",
        "        },\n",
        "    ]\n",
        "    (coords, distances) = define_data(\n",
        "        [(c[\"latitude\"], c[\"longitude\"]) for c in otherLocs],\n",
        "        [c[\"city\"] for c in otherLocs],\n",
        "    )\n",
        "    return (coords, distances)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_EVhjuNcGidp"
      },
      "source": [
        "# AMPL solution method\n",
        "To solve the TSP model, we need to make sure it has no subtours; since enumerating them all beforehand is basically impossible, we choose a reactive approach. This function solves the model (with the current set of subtours cut out) and checks if the obtained solution has any subtour.\n",
        "If it does, it displays it and return False, otherwise the solution is a valid path, simply return True.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "6uNINNANGhtJ"
      },
      "outputs": [],
      "source": [
        "def solve_ampl(map) -> bool:\n",
        "    nSubtoursParam = ampl.get_parameter(\"nSubtours\")\n",
        "    SubtoursSet = ampl.get_set(\"SUB\")\n",
        "    allsubtours = [\n",
        "        ampl.get_set(\"SUB\")[i].to_list() for i in range(1, int(nSubtoursParam.value()))\n",
        "    ]\n",
        "\n",
        "    # Solve the model\n",
        "    ampl.solve()\n",
        "\n",
        "    # Get solution\n",
        "    print(\"Solved, getting solution\")\n",
        "    length = ampl.get_objective(\"Tour_Length\").value()\n",
        "    print(ampl.get_nodes())\n",
        "    print(ampl.get_arcs())\n",
        "\n",
        "    subtours = find_subtours(ampl.get_arcs(), ampl.get_nodes())\n",
        "    # If we have only one tour, the solution is valid\n",
        "    if len(subtours) <= 1:\n",
        "        print(f\"\\nFound only {len(subtours)} subtours, returning\")\n",
        "        map.log(f\"Length={length}. No subtour found, shortest valid path.\")\n",
        "        return True\n",
        "\n",
        "    # Else:\n",
        "    print(f\"\\nFound {len(subtours)} subtours, plotting them and adding cuts\")\n",
        "    map.log(f\"Length={length}. {len(subtours)} subtours, adding cuts\")\n",
        "\n",
        "    # Plot the subtours\n",
        "    coords = ampl.get_coords()\n",
        "    for s in subtours:\n",
        "        vt = s.copy()\n",
        "        vt.append(vt[0])\n",
        "        vt = as_steps(vt)\n",
        "        vt = [(coords[i], coords[j]) for i, j in vt]\n",
        "        map.add_arcs(vt)\n",
        "\n",
        "    # Add the current tours to the list of subtours\n",
        "    allsubtours.extend(subtours)\n",
        "    # And add those to the constraints by assigning the values to\n",
        "    # the parameter and the set\n",
        "    nSubtoursParam.set(len(allsubtours))\n",
        "    for i, tour in enumerate(allsubtours):\n",
        "        print(f\"Adding cut: {tour}\")\n",
        "        SubtoursSet[i + 1].set_values(tour)\n",
        "    return False"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uftSUdTh9eZY"
      },
      "source": [
        "# \"Glue\" functions\n",
        "These functions help glueing the GUI and python data processing part with the underlying AMPL object.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "KgQorEV_VQQm"
      },
      "outputs": [],
      "source": [
        "SOLVER = \"highs\"\n",
        "from amplpy import DataFrame as aDF\n",
        "\n",
        "\n",
        "def data_2_AMPL(coordinates: pd.DataFrame, distances: pd.DataFrame):\n",
        "    # Convert the dataframes to the specific dataframes expected by AMPL and assings\n",
        "    # those values to the set of NODES, the params longitude and latitude, and the parameter distances\n",
        "    ampl.eval(\"reset data;\")\n",
        "    # Convert to amplpy dataframes\n",
        "    coordinates = aDF.from_pandas(coordinates, index_names=[\"POINT\"])\n",
        "    distances = aDF.from_dict(\n",
        "        distances, index_names=[\"orig\", \"dest\"], column_names=[\"distance\"]\n",
        "    )\n",
        "    ampl.set_data(coordinates, set_name=\"NODES\")\n",
        "    ampl.set_data(distances)\n",
        "\n",
        "\n",
        "def solve(map: MyMap, alreadySolving: bool):\n",
        "    # Main solve procedure; if we're not in the middle of a solution process,\n",
        "    # reads the data from the map and pass it to AMPL then solve it.\n",
        "    # Otherwise just continue the ongoing solution process\n",
        "    if not alreadySolving:\n",
        "        map.set_solving_status(\"solving\")\n",
        "        nodes = map.get_points()\n",
        "        if len(nodes) <= 2:\n",
        "            map.log(\"Trivial problem, add more points to solve.\")\n",
        "            map.set_solving_status(\"finished\")\n",
        "            return\n",
        "        print(f\"Solving for {len(nodes)} points\")\n",
        "        (coords, distances) = define_data(nodes)\n",
        "        data_2_AMPL(coords, distances)\n",
        "        ampl.option[\"solver\"] = SOLVER\n",
        "    continue_solve(map)\n",
        "\n",
        "\n",
        "def continue_solve(map: MyMap):\n",
        "    # Continue the ongoing solution process\n",
        "    # Clear the previous solution from the map\n",
        "    map.clean(markers=False)\n",
        "    # Call AMPL to solve the current problem instance\n",
        "    status = solve_ampl(map)\n",
        "    # Status==True if the solution has no subtours\n",
        "    if status:\n",
        "        # If the solution is valid (no subtours), \"inform\" the map object and\n",
        "        # display the solution\n",
        "        map.set_solving_status(\"finished\")\n",
        "        arcs = ampl.get_arcs()\n",
        "        coords = ampl.get_coords()\n",
        "        tours = [(coords[i], coords[j]) for i, j in arcs]\n",
        "        print(f\"Solution has {len(tours)} arcs;\")\n",
        "        print(arcs)\n",
        "        map.add_arcs(tours)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jw2KIbwkEPpA"
      },
      "source": [
        "## Show the UI\n",
        "These commands load a sample dataset and add it to the map"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "rZOHbEtJBNcq"
      },
      "outputs": [],
      "source": [
        "# Create the GUI and use the solve function defined here to actually solve\n",
        "# the model\n",
        "m = MyMap(solve)\n",
        "# Get sample data\n",
        "(coord, dist) = sample_data()\n",
        "# Add it to the map\n",
        "m.add_points(coord[[\"latitude\", \"longitude\"]].to_records(index=False))\n",
        "# Show the GUI\n",
        "m.render()"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3 (ipykernel)",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.10.12"
    },
    "vscode": {
      "interpreter": {
        "hash": "ee4198aac13dae9b6fccd443041680d99c2643c4956ef7c80ff6dcc0057cb523"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}