{ "cells": [ { "cell_type": "code", "execution_count": null, "metadata": { "tags": [ "remove-cell" ] }, "outputs": [], "source": [ "import sys\n", "\n", "sys.path.insert(1, \"../../\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Traveling Salesperson Problem\n", "\n", "As an example of using the Amplify SDK, we will explain how to solve the traveling salesperson problem (TSP) with the Amplify SDK.\n", "The TSP is a combinatorial optimization problem that, given a set of cities, finds the shortest path that starts in one city, visits all the cities once, and returns to the first city." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Formulating the traveling salesperson problem\n", "\n", "Let the number of cities be denoted by `NUM_CITIES`.\n", "\n", "### Variables\n", "\n", "First, we will use the `NUM_CITIES` binary (0-1) variables to represent which of the `NUM_CITIES` cities is to be visited. We represent a visit to city `i` by setting the `i`-th binary variable to 1 and all other variables to 0.\n", "\n", "For example, if the number of cities is 5 and the values of the 5 binary variables are `[0, 0, 0, 0, 1, 0]`, this is an expression for visiting city 3, since only the variable with index 3 is 1. This method of expressing which of the n options we choose by setting one of the n binary variables to 1 is called one-hot encoding, and is often used in machine learning and other applications.\n", "\n", "```{csv-table}\n", ":header-rows: 1\n", "\n", "\"City 0\", \"City 1\", \"City 2\", \"City 3\", \"City 4\"\n", "0, 0, 0, 1, 0\n", "```\n", "\n", "Since in the TSP, the salesperson visits cities one at a time and returns to the first city at the end, the number of visits to cities is `NUM_CITIES + 1` times, including the first and last. So we have `(NUM_CITIES + 1) * NUM_CITIES`{l=python} binary variables. For example, the following example represents a closed path that visits five cities in the order city 3 → city 1 → city 4 → city 0 → city 2 → city 3.\n", "\n", "```{csv-table} Binary variable table\n", ":header-rows: 1\n", "\n", "\"City 0\", \"City 1\", \"City 2\", \"City 3\", \"City 4\"\n", "0, 0, 0, 1, 0\n", "0, 1, 0, 0, 0\n", "0, 0, 0, 0, 1\n", "1, 0, 0, 0, 0\n", "0, 0, 1, 0, 0\n", "0, 0, 0, 1, 0\n", "```\n", "\n", "(tsp-formulation-constraint)=\n", "\n", "### Constraint\n", "\n", "In the \"binary variables table\" above, `(NUM_CITIES + 1) * NUM_CITIES`{l=python} binary variables can take any value of 0 or 1, but such a path is not necessarily a close path representation. For example, having all binary variables as one yields no (closed) path. Therefore, it is necessary to impose constraints appropriately on the binary variables. Three types of constraints are required:\n", "\n", "1. The first and last rows of the binary variable table must have the same value.\n", "2. Each row of the binary variable table must have exactly one variable that is 1.\n", "3. Each column of the binary variable table must have exactly one variable that is 1, except for the last row.\n", "\n", "Conversely, if there is a binary variable table that satisfies the above three constraints, it represents a closed path.\n", "\n", "(tsp-formulation-objective)=\n", "Objective function\n", "\n", "The objective of the TSP is to find the shortest route that visits all cities once and returns to the start city. Therefore, the objective function is the path length of such a route.\n", "\n", "Suppose the distance between city i and city j is `d[i, j]`. The current goal is to find the path length of the closed route from the values in the binary variable table.\n", "\n", "If the binary variable table values are known, you can find the path length of the route in the following pseudo-code. Suppose the binary variables in the 'k' rows and 'i' columns can be written as 'q[k, i]`.\n", "\n", "```\n", "route_length = 0\n", "\n", "for k in range(NUM_CITIES):\n", " for i in range(NUM_CITIES):\n", " for j in range(NUM_CITIES):\n", " route_length += (d[i, j] if q[k, i] == 1 and q[k+1, j] == 1 else 0)\n", "```\n", "\n", "However, when formulating in the Amplify SDK, we only know that each `q[k, i]` is a binary variable, and we do not yet know what value it will take, so we cannot make the conditional decision ``if q[k, i] == 1 and q[k+1, j] == 1``{l=python}. Only the addition and multiplication of binary variables and numbers can represent the objective function.\n", "\n", "Now, let's recall that the product of two binary variables `q[k, i] * q[k+1, j]` is 1 if `q[k, i] == 1 and q[k+1, j] == 1`{l=python} is true and 0 if false. Then the objective function can be implemented as follows.\n", "\n", "```\n", "route_length = 0\n", "\n", "for k in range(NUM_CITIES):\n", " for i in range(NUM_CITIES):\n", " for j in range(NUM_CITIES):\n", " route_length += d[i, j] * q[k, i] * q[k+1, j]\n", "```\n", "\n", "### Formulation\n", "\n", "Writing down the above discussion in mathematical form, the formulation of the TSP in terms of binary variables `(NUM_CITIES + 1) * NUM_CITIES` can be written as:\n", "\n", "```{math}\n", "\\begin{align}\n", "&\\text{minimize} \\quad & \\sum_{0 \\leq i, j, k < N} d_{i, j} q_{k, i} q_{k+1, j} & \\\\\n", "&\\text{subject to} \\quad & q_{N - 1, i} = q_{0, i} \\quad & \\text{for} \\quad 0 \\leq i < N, \\\\\n", "& & \\sum_{0 \\leq i} q_{k, i} = 1 \\quad & \\text{for} \\quad 0 \\leq k < N, \\\\\n", "& & \\sum_{0 \\leq k} q_{k, i} = 1 \\quad & \\text{for} \\quad 0 \\leq i < N.\n", "\\end{align}\n", "```\n", "\n", "However, for notational convenience, the number of cities `NUM_CITIES` is denoted as $N$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Creating problem\n", "\n", "First, let's create a problem. Let the number of cities be `NUM_CITIES`, and we will randomly select each city's x and y coordinates from the integers 0~100. In the following, we name city 0, city 1, ..., and city `NUM_CITIES - 1`.\n", "\n", "This sample code sets the number of cities to 5 for simplicity." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import numpy as np" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "tags": [ "remove-cell" ] }, "outputs": [], "source": [ "np.set_printoptions(precision=3)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "NUM_CITIES = 5" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "rng = np.random.default_rng()\n", "\n", "x = rng.integers(0, 100, NUM_CITIES)\n", "y = rng.integers(0, 100, NUM_CITIES)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Next, we will create a distance matrix representing the distances between cities. Here, the distances are Euclidean distances. The output is a NumPy array of `n * n`{l=python}, where the elements in the `i` row `j` columns represent the distance between city `i` and city `j`, i.e. `(x[i] - x[j]) ** 2 + (y[i] - y[j] ** 2) ** 0.5`{l=python}.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "distance = (\n", " (x[:, np.newaxis] - x[np.newaxis, :]) ** 2\n", " + (y[:, np.newaxis] - y[np.newaxis, :]) ** 2\n", ") ** 0.5\n", "\n", "print(distance)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Formulation with the Amplify SDK\n", "\n", "We will now formulate the problem with the Amplify SDK.\n", "\n", "### Variable generation [{octicon}`link`](variables.md)\n", "\n", "First, we create the decision variables. The Amplify SDK allows you to generate variables in the form of the two-dimensional array by using {py:class}`~amplify.VariableGenerator`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from amplify import VariableGenerator\n", "\n", "gen = VariableGenerator()\n", "q = gen.array(\"Binary\", (NUM_CITIES + 1, NUM_CITIES))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The binary variables `q` look like the following." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "q" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(tsp-constraint)=\n", "\n", "### Creating constraints [{octicon}`link`](constraint.md)\n", "\n", "Next, we create constraints. As described [above](#tsp-formulation-constraint), there are three types of constraints.\n", "\n", "1. The first and last rows of the binary variable table must have the same value.\n", "2. Each row of the binary variable table must have exactly one variable that is 1.\n", "3. Each column of the binary variable table must have exactly one variable that is 1, except for the last row.\n", "\n", "#### First constraint\n", "\n", "Create the first constraint \"the first and last rows of the binary variable table must have the same value.\" is constructed here. We want to fix the last row to the same value as the first row, so we assign the first row to the last row of `q`. The first row of `q` can be written as `q[0]` and the last row of `q` as `q[-1]`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "q[-1] = q[0]\n", "\n", "q" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can now express the first constraint.\n", "\n", "```{attention}\n", "If you fix variables by assignment, do so before constructing the objective function or other constraints.\n", "```\n", "\n", "In subsequent constraint construction, we will not need to consider the last row of the binary variable array `q`, so we will create an array with the `NUM_CITIES` rows cut out from the top of `q`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "q_upper = q[:-1]\n", "\n", "q_upper" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Second constraint\n", "\n", "We now create the second constraint, \"each row of the binary variable table must have exactly one variable that is 1.\" If you want to impose the constraint that exactly one of several binary variables is 1, use the {py:func}`~amplify.one_hot` function. If you want to impose the one-hot constraint on each row of a variable array, set 1 to the `axis` keyword argument of the {py:func}`~amplify.one_hot` function." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from amplify import one_hot\n", "\n", "constraints2 = one_hot(q_upper, axis=1)\n", "\n", "constraints2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`NUM_CITIES` (= 5) constraints were generated at once." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Third constraint\n", "\n", "We then create the third constraint \"each column of the binary variable table must have exactly one variable that is 1, except for the last row.\" As with the second constraint, we use the {py:func}`~amplify.one_hot` function. If you want to impose a one-hot constraint on each column of the variable array, give 0 to the `axis` keyword argument of the {py:func}`~amplify.one_hot` function." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "constraints3 = one_hot(q_upper, axis=0)\n", "\n", "constraints3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(tsp-objective)=\n", "\n", "### Creating the objective function [{octicon}`link`](objective.md)\n", "\n", "Next, we create the objective function. As mentioned [above](#tsp-formulation-objective), the objective function is the path length of the route and can be written as follows." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "route_length = 0\n", "\n", "for k in range(NUM_CITIES):\n", " for i in range(NUM_CITIES):\n", " for j in range(NUM_CITIES):\n", " route_length += distance[i, j] * q[k, i] * q[k + 1, j]\n", "\n", "print(route_length)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Alternatively, the following code creates the same objective function. This code is faster because it takes full advantage of the Amplify SDK's features and is recommended for those familiar with the NumPy library. See [](optimization.md) for details." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from amplify import Poly, einsum\n", "\n", "q1 = q[:-1]\n", "q2 = q[1:]\n", "route_length: Poly = einsum(\"ij,ki,kj->\", distance, q1, q2) # type: ignore\n", "\n", "print(route_length)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(tsp-model)=\n", "\n", "### Creating a combinatorial optimization model [{octicon}`link`](model.md)\n", "\n", "We now create a combinatorial optimization model by combining the objective function and constraints constructed in \"[creating constraints](#tsp-constraint)\" and \"[creating the objective function](#tsp-objective)\"." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "model = route_length + (constraints2 + constraints3) * np.max(distance)\n", "\n", "print(model)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We multiply the constraints by the maximum value of the distance matrix to give weight to the constraints. In Amplify AE, the solver used in this example, unless appropriate weights are specified for the constraints, the solver will move toward reducing the objective function rather than trying to satisfy the constraints and will not be able to find a feasible solution. See [](penalty.md) for details." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Creating a solver client [{octicon}`link`](clients.md)\n", "\n", "Here, we will create a solver client, specify a solver for solving, and set solver parameters. The Amplify SDK supports various solvers. Here, we will use Amplify AE. The solver client class for Amplify AE is the {py:class}`~amplify.FixstarsClient` class." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from amplify import FixstarsClient\n", "\n", "client = FixstarsClient()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will set an API token required for running Amplify AE.\n", "\n", "```{tip}\n", "[Register as a user](https://amplify.fixstars.com/en/register) to obtain a free API token that you can use for evaluation and validation purposes.\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "tags": [ "skip-execution" ] }, "outputs": [], "source": [ "client.token = \"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\"" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "tags": [ "remove-cell" ] }, "outputs": [], "source": [ "client.token = \"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We also need to set the timeout value of the solver; the unit of the timeout value of Amplify AE is ms, but since the unit of the timeout value varies from solver to solver, the timeout value can be specified uniformly by using {py:mod}`datetime` module." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import datetime\n", "\n", "client.parameters.timeout = datetime.timedelta(seconds=1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This completes the solver setup." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Executing the solver [{octicon}`link`](solve.md)\n", "\n", "Let's execute the solver using the created combinatorial optimization model and the solver client to solve the traveling salesperson problem." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "tags": [] }, "outputs": [], "source": [ "from amplify import solve\n", "\n", "result = solve(model, client)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The value of the objective function, i.e., the length of the closed route, can be obtained as follows." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "result.best.objective" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The values of the variables in the optimal solution can be obtained in the form of a multidimensional NumPy array as follows." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "q_values = q.evaluate(result.best.values)\n", "\n", "print(q_values)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Checking the result\n", "\n", "This is enough for a tutorial on the Amplify SDK, but we want to visualize the result." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "\n", "%matplotlib inline" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "First, we visualize the locations of the cities." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "plt.scatter(x, y)\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Lastly, we visualize the route. Since `q_values` can be considered a substitution matrix (with one row added to the end), we can sort the cities in the order they are visited on the route by multiplying the ordered vector of cities by `q_values` from the left." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "route_x = q_values @ x # x-coordinate of the itinerary\n", "route_y = q_values @ y # y-coordinate of the itinerary\n", "\n", "plt.scatter(x, y)\n", "plt.plot(route_x, route_y)\n", "plt.show()" ] } ], "metadata": { "kernelspec": { "display_name": "amplify-lrEeNlW4", "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" } }, "nbformat": 4, "nbformat_minor": 2 }