formulate_p-dispersion.ipynb

formulate_p-dispersion.ipynb

{
  "cells": [
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Demonstrating the $p$-Dispersion formulation found in Maliszewski, Kuby, and Horner (2012)\n* **Maliszewski, Paul J., Michael J. Kuby, and Mark W. Horner.** 2012. A comparison of multi-objective spatial dispersion models for managing critical assets in urban areas. Computers, Environment and Urban Systems. 36 (4):331-341."
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2022-08-04T02:56:01.929129Z",
          "end_time": "2022-08-04T02:56:01.975545Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "%load_ext watermark\n%watermark",
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": "Last updated: 2022-08-03T22:56:01.961812-04:00\n\nPython implementation: CPython\nPython version       : 3.10.4\nIPython version      : 8.2.0\n\nCompiler    : Clang 12.0.1 \nOS          : Darwin\nRelease     : 21.6.0\nMachine     : x86_64\nProcessor   : i386\nCPU cores   : 8\nArchitecture: 64bit\n\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2022-08-04T02:56:01.978749Z",
          "end_time": "2022-08-04T02:56:02.061393Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "import numpy\n%watermark -w\n%watermark -iv",
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": "Watermark: 2.3.0\n\njson : 2.0.9\nnumpy: 1.22.3\n\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Consider a synthetic symmetric cost matrix $d_{ij}$"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2022-08-04T02:56:02.066074Z",
          "end_time": "2022-08-04T02:56:02.077256Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "d_ij = numpy.array(\n    [[0, 9, 2, 6], [9, 0, 4, 7], [2, 4, 0, 8], [6, 7, 8, 0]]\n)\nd_ij",
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 3,
          "data": {
            "text/plain": "array([[0, 9, 2, 6],\n       [9, 0, 4, 7],\n       [2, 4, 0, 8],\n       [6, 7, 8, 0]])"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2022-08-04T02:56:02.080237Z",
          "end_time": "2022-08-04T02:56:02.085502Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "rows, cols = d_ij.shape\nrows, cols",
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 4,
          "data": {
            "text/plain": "(4, 4)"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Currently in cell \"166\":"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2022-08-04T02:56:02.088324Z",
          "end_time": "2022-08-04T02:56:02.093417Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "for i in range(rows):\n    for j in range(cols):\n        if i == j:\n            continue\n        else:\n            print(i,j)",
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": "0 1\n0 2\n0 3\n1 0\n1 2\n1 3\n2 0\n2 1\n2 3\n3 0\n3 1\n3 2\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "#### Here we have set an equality condition to continue if `i==j`. However, the formulation stipulates that we should skip if $i$ greater than $j$.\n\n## What we are looking for:"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2022-08-04T02:56:02.096092Z",
          "end_time": "2022-08-04T02:56:02.099599Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "for i in range(rows):\n    for j in range(cols):\n        if j <= i:\n            continue\n        else:\n            print(i,j)",
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": "0 1\n0 2\n0 3\n1 2\n1 3\n2 3\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Generate the program in LP format"
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2022-08-04T02:56:02.102173Z",
          "end_time": "2022-08-04T02:56:02.104664Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "p = 2\nM = d_ij.max()",
      "execution_count": 7,
      "outputs": []
    },
    {
      "metadata": {
        "ExecuteTime": {
          "start_time": "2022-08-04T02:56:02.107093Z",
          "end_time": "2022-08-04T02:56:02.113055Z"
        },
        "trusted": true
      },
      "cell_type": "code",
      "source": "pdisp_form = \"Maximize\\n\\tD\\nSubject To\\n\\t\"\n# facility constraint\npdisp_form += \" + \".join([f\"Y{i}\" for i in range(rows)]) + f\" = {p}\\n\"\n# inter-facility distance constraints\nfor i in range(rows):\n    for j in range(cols):\n        if j <= i:\n            continue\n        else:\n            dij = d_ij[i,j]\n            pdisp_form += f\"\\t{dij} + {M}(2 - Y{i} - Y{j}) >= D\\n\"\n# binary constraints\npdisp_form += \"Variables\\n\"\npdisp_form += \"\\n\".join([f\"\\tY{i} = {{0,1}}\" for i in range(rows)])\nprint(pdisp_form)",
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": "Maximize\n\tD\nSubject To\n\tY0 + Y1 + Y2 + Y3 = 2\n\t9 + 9(2 - Y0 - Y1) >= D\n\t2 + 9(2 - Y0 - Y2) >= D\n\t6 + 9(2 - Y0 - Y3) >= D\n\t4 + 9(2 - Y1 - Y2) >= D\n\t7 + 9(2 - Y1 - Y3) >= D\n\t8 + 9(2 - Y2 - Y3) >= D\nVariables\n\tY0 = {0,1}\n\tY1 = {0,1}\n\tY2 = {0,1}\n\tY3 = {0,1}\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "### Here we can see that there is one facility constraint, 6 inter-facility distance constraints, and 4 binary constraints."
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "conda-env-py310_spopt-py",
      "display_name": "Python [conda env:py310_spopt]",
      "language": "python"
    },
    "language_info": {
      "name": "python",
      "version": "3.10.4",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "gist": {
      "id": "",
      "data": {
        "description": "formulate_p-dispersion.ipynb",
        "public": true
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}