{
    "nbformat": 4,
    "nbformat_minor": 5,
    "metadata": {
        "kernelspec": {
            "display_name": "Python",
            "language": "python",
            "name": "python"
        },
        "language_info": {
            "name": "python"
        }
    },
    "cells": [
        {
            "id": "b388111c",
            "cell_type": "markdown",
            "source": "<div class='alert alert-warning'>\n\nSciPy's interactive examples with Jupyterlite are experimental and may not always work as expected. Execution of cells containing imports may result in large downloads (up to 60MB of content for the first import from SciPy). Load times when importing from SciPy may take roughly 10-20 seconds. If you notice any problems, feel free to open an [issue](https://github.com/scipy/scipy/issues/new/choose).\n\n</div>",
            "metadata": {}
        },
        {
            "id": "bc2daa99",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "import numpy as np\nfrom scipy.optimize import quadratic_assignment\nrng = np.random.default_rng()\nA = np.array([[0, 80, 150, 170], [80, 0, 130, 100],\n              [150, 130, 0, 120], [170, 100, 120, 0]])\nB = np.array([[0, 5, 2, 7], [0, 0, 3, 8],\n              [0, 0, 0, 3], [0, 0, 0, 0]])\nres = quadratic_assignment(A, B, options={'rng': rng})\nprint(res)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "     fun: 3260\n col_ind: [0 3 2 1]\n     nit: 9"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "a7957778",
            "cell_type": "markdown",
            "source": "The see the relationship between the returned ``col_ind`` and ``fun``,\nuse ``col_ind`` to form the best permutation matrix found, then evaluate\nthe objective function $f(P) = trace(A^T P B P^T )$.\n",
            "metadata": {}
        },
        {
            "id": "e0a5c6ab",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "perm = res['col_ind']\nP = np.eye(len(A), dtype=int)[perm]\nfun = np.trace(A.T @ P @ B @ P.T)\nprint(fun)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "3260"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "c342a9b9",
            "cell_type": "markdown",
            "source": "Alternatively, to avoid constructing the permutation matrix explicitly,\ndirectly permute the rows and columns of the distance matrix.\n",
            "metadata": {}
        },
        {
            "id": "2d25003b",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "fun = np.trace(A.T @ B[perm][:, perm])\nprint(fun)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "3260"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "63d7fea0",
            "cell_type": "markdown",
            "source": "Although not guaranteed in general, ``quadratic_assignment`` happens to\nhave found the globally optimal solution.\n",
            "metadata": {}
        },
        {
            "id": "8350f64c",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "from itertools import permutations\nperm_opt, fun_opt = None, np.inf\nfor perm in permutations([0, 1, 2, 3]):\n    perm = np.array(perm)\n    fun = np.trace(A.T @ B[perm][:, perm])\n    if fun < fun_opt:\n        fun_opt, perm_opt = fun, perm\nprint(np.array_equal(perm_opt, res['col_ind']))",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "True"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "9580507e",
            "cell_type": "markdown",
            "source": "Here is an example for which the default method,\n:ref:`'faq' <optimize.qap-faq>`, does not find the global optimum.\n",
            "metadata": {}
        },
        {
            "id": "99e907f7",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "A = np.array([[0, 5, 8, 6], [5, 0, 5, 1],\n              [8, 5, 0, 2], [6, 1, 2, 0]])\nB = np.array([[0, 1, 8, 4], [1, 0, 5, 2],\n              [8, 5, 0, 5], [4, 2, 5, 0]])\nres = quadratic_assignment(A, B, options={'rng': rng})\nprint(res)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "     fun: 178\n col_ind: [1 0 3 2]\n     nit: 13"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "a339185f",
            "cell_type": "markdown",
            "source": "If accuracy is important, consider using  :ref:`'2opt' <optimize.qap-2opt>`\nto refine the solution.\n",
            "metadata": {}
        },
        {
            "id": "9188167d",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "guess = np.array([np.arange(len(A)), res.col_ind]).T\nres = quadratic_assignment(A, B, method=\"2opt\",\n    options = {'rng': rng, 'partial_guess': guess})\nprint(res)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "     fun: 176\n col_ind: [1 2 3 0]\n     nit: 17"
                    },
                    "execution_count": null
                }
            ]
        }
    ]
}