ampl-lecture/transp_lecture.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Transportation problem\n",
        "[![transp_lecture.ipynb](https://img.shields.io/badge/github-%23121011.svg?logo=github)](https://github.com/ampl/colab.ampl.com/blob/master/ampl-lecture/transp_lecture.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/ampl-lecture/transp_lecture.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/ampl-lecture/transp_lecture.ipynb) [![Gradient](https://assets.paperspace.io/img/gradient-badge.svg)](https://console.paperspace.com/github/ampl/colab.ampl.com/blob/master/ampl-lecture/transp_lecture.ipynb) [![Open In SageMaker Studio Lab](https://studiolab.sagemaker.aws/studiolab.svg)](https://studiolab.sagemaker.aws/import/github/ampl/colab.ampl.com/blob/master/ampl-lecture/transp_lecture.ipynb) [![Hits](https://h.ampl.com/https://github.com/ampl/colab.ampl.com/blob/master/ampl-lecture/transp_lecture.ipynb)](https://colab.ampl.com)\n",
        "\n",
        "Description: an AMPL model for the transportation problem\n",
        "\n",
        "Tags: ampl-only, ampl-lecture\n",
        "\n",
        "Notebook author: Marcos Dominguez Velad <<marcos@ampl.com>>\n",
        "\n",
        "Model author: N/A\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Install dependencies\n",
        "%pip install -q amplpy"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Google Colab & Kaggle integration\n",
        "from amplpy import AMPL, ampl_notebook\n",
        "\n",
        "ampl = ampl_notebook(\n",
        "    modules=[\"coin\"],  # modules to install\n",
        "    license_uuid=\"default\",  # license to use\n",
        ")  # instantiate AMPL object and register magics"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "This notebook provides the implementation of the transportation problem described in the book *AMPL: A Modeling Language for Mathematical Programming*\n",
        "by Robert Fourer, David M. Gay, and Brian W. Kernighan.\n",
        "\n",
        "## Example: Transportation problem\n",
        "Two fundamental sets of objects underlie the transportation problem: the sources or origins (mills, in our example) and the destinations (factories). Thus we begin the AMPL model with a declaration of these two sets:\n",
        "```ampl\n",
        "set ORIG;\n",
        "set DEST;\n",
        "```\n",
        "There is a supply of something at each origin (tons of steel coils produced, in our case), and a demand for the same thing at each destination (tons of coils ordered). AMPL defines nonnegative quantities like these with param statements indexed over a set; in this case we add one extra refinement, a check statement to test the data for validity:\n",
        "```ampl\n",
        "param supply {ORIG} >= 0;\n",
        "param demand {DEST} >= 0;\n",
        "check: sum {i in ORIG} supply[i] = sum {j in DEST} demand[j];\n",
        "```\n",
        "The check statement says that the sum of the supplies has to equal the sum of the demands. The way that our model is to be set up, there can't possibly be any solutions unless this condition is satisfied. By putting it in a check statement, we tell AMPL to test this condition after reading the data, and to issue an error message if it is violated.\n",
        "\n",
        "For each combination of an origin and a destination, there is a transportation cost and a variable representing the amount transported. Again, the ideas from previous chapters are easily adapted to produce the appropriate AMPL statements:\n",
        "```ampl\n",
        "param cost {ORIG,DEST} >= 0;\n",
        "var Trans {ORIG,DEST} >= 0;\n",
        "```\n",
        "For a particular origin `i` and destination `j`, we ship `Trans[i,j]` units from `i` to `j`, at a cost of `cost[i,j]` per unit; the total cost for this pair is\n",
        "```ampl\n",
        "cost[i,j] * Trans[i,j]\n",
        "```\n",
        "Adding over all pairs, we have the objective function:\n",
        "```ampl\n",
        "minimize Total_Cost:\n",
        "   sum {i in ORIG, j in DEST} cost[i,j] * Trans[i,j];\n",
        "```\n",
        "which could also be written as\n",
        "```ampl\n",
        "sum {j in DEST, i in ORIG} cost[i,j] * Trans[i,j];\n",
        "```\n",
        "or as\n",
        "```ampl\n",
        "sum {i in ORIG} sum {j in DEST} cost[i,j] * Trans[i,j];\n",
        "```\n",
        "As long as you express the objective in some mathematically correct way, AMPL will sort out the terms.\n",
        "\n",
        "It remains to specify the two collections of constraints, those at the origins and those at the destinations. If we name these collections Supply and Demand, their declarations will start as follows:\n",
        "```ampl\n",
        "subject to Supply {i in ORIG}: ...\n",
        "subject to Demand {j in DEST}: ...\n",
        "```\n",
        "To complete the `Supply` constraint for origin `i`, we need to say that the sum of all shipments out of `i` is equal to the supply available. Since the amount shipped out of `i` to a particular destination `j` is `Trans[i,j]`, the amount shipped to all destinations must be\n",
        "```ampl\n",
        "sum {j in DEST} Trans[i,j]\n",
        "```\n",
        "Since we have already defined a parameter supply indexed over origins, the amount available at i is supply[i]. Thus the constraint is\n",
        "```ampl\n",
        "subject to Supply {i in ORIG}:\n",
        "    sum {j in DEST} Trans[i,j] = supply[i];\n",
        "```\n",
        "(Note that the names supply and Supply are unrelated; AMPL distinguishes upper and lower case.) The other collection of constraints is much the same, except that the roles of `i` in `ORIG`, and `j` in `DEST`, are exchanged, and the sum equals `demand[j]`.\n",
        "\n",
        "We have been consistent in using the index i to run over the set ORIG, and the index j to run over DEST. This is not an AMPL requirement, but such a convention makes it easier to read a model. You may name your own indices whatever you like, but keep in mind that the scope of an index - the part of the model where it has the same meaning - is to the end of the expression that defines it. Thus in the `Demand` constraint\n",
        "```ampl\n",
        "subject to Demand {j in DEST}:\n",
        "\tsum {i in ORIG} Trans[i,j] = demand[j];\n",
        "```\n",
        "The following files describe the model and a particular data file for this problem."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%writefile transp.mod\n",
        "set ORIG;   # origins\n",
        "set DEST;   # destinations\n",
        "\n",
        "param supply {ORIG} >= 0;   # amounts available at origins\n",
        "param demand {DEST} >= 0;   # amounts required at destinations\n",
        "\n",
        "   check: sum {i in ORIG} supply[i] = sum {j in DEST} demand[j];\n",
        "\n",
        "param cost {ORIG,DEST} >= 0;   # shipment costs per unit\n",
        "var Trans {ORIG,DEST} >= 0;    # units to be shipped\n",
        "\n",
        "minimize Total_Cost:\n",
        "   sum {i in ORIG, j in DEST} cost[i,j] * Trans[i,j];\n",
        "\n",
        "subject to Supply {i in ORIG}:\n",
        "   sum {j in DEST} Trans[i,j] = supply[i];\n",
        "\n",
        "subject to Demand {j in DEST}:\n",
        "   sum {i in ORIG} Trans[i,j] = demand[j];"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%writefile transp.dat\n",
        "data;\n",
        "\n",
        "param: ORIG:  supply :=  # defines set \"ORIG\" and param \"supply\"\n",
        "        GARY   1400\n",
        "        CLEV   2600\n",
        "        PITT   2900 ;\n",
        "\n",
        "param: DEST:  demand :=  # defines \"DEST\" and \"demand\"\n",
        "        FRA     900\n",
        "        DET    1200\n",
        "        LAN     600\n",
        "        WIN     400\n",
        "        STL    1700\n",
        "        FRE    1100\n",
        "        LAF    1000 ;\n",
        "\n",
        "param cost:\n",
        "         FRA  DET  LAN  WIN  STL  FRE  LAF :=\n",
        "   GARY   39   14   11   14   16   82    8\n",
        "   CLEV   27    9   12    9   26   95   17\n",
        "   PITT   24   14   17   13   28   99   20 ;"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "model transp.mod;\n",
        "data transp.dat;\n",
        "option solver cbc;\n",
        "solve;\n",
        "display Trans;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The minimum cost is still 196200, but it is achieved in a different way. Alternative optimal solutions such as these are often exhibited by transportation problems, particularly when the coefficients in the objective function are round numbers.\n",
        "\n",
        "Unfortunately, there is no easy way to characterize all the optimal solutions. You may be able to get a better choice of optimal solution by working with several objectives.\n",
        "\n",
        "## Other interpretations of the transportation model\n",
        "\n",
        "As the name suggests, a transportation model is applicable whenever some material is being shipped from a set of origins to a set of destinations. Given certain amounts available at the origins, and required at the destinations, the problem is to meet the requirements at a minimum shipping cost.\n",
        "\n",
        "Viewed more broadly, transportation models do not have to be concerned with the shipping of \"materials\". They can be applied to the transportation of anything, provided that the quantities available and required can be measured in some units, and that the transportation cost per unit can be determined. They might be used to model the shipments of automobiles to dealers, for example, or the movement of military personnel to new assignments.\n",
        "\n",
        "In an even broader view, transportation models need not deal with \"shipping\" at all. The quantities at the origins may be merely associated with various destinations, while the objective measures some value of the association that has nothing to do with actually moving anything. Often the result is referred to as an ***assignment*** model.\n",
        "\n",
        "As one particularly well-known example, consider a department that needs to assign some number of people to an equal number of offices. The origins now represent individual people, and the destinations represent individual offices. Since each person is assigned one office, and each office is occupied by one person, all of the parameter values `supply[i]` and `demand[j]` are 1. We interpret `Trans[i,j]` as the \"amount\" of person `i` that is assigned to office `j`; that is, if `Trans[i,j]` is 1 then person i will occupy office j, while if `Trans[i,j]` is 0 then person i will not occupy office j.\n",
        "\n",
        "What of the objective? One possibility is to ask people to rank the offices, giving their first choice, second choice, and so forth. Then we can let `cost[i,j]` be the rank that person i gives to office `j`. This convention lets each objective function term `cost[i,j]*Trans[i,j]` represent the preference of person i for office j, if person i is assigned to office j (`Trans[i,j]` equals 1), or zero if person i is not assigned to office j (`Trans[i,j]` equals 0). Since the objective is the sum of all these terms, it must equal the sum of all the nonzero terms, which is the sum of everyone's rankings for the offices to which they were assigned. By minimizing this sum, we can hope to find an assignment that will please a lot of people.\n",
        "\n",
        "To use the transportation model for this purpose, we need only supply the appropriate data. We are presenting an example with 11 people to be assigned to 11 offices. The default option has been used to set all the supply and demand values to 1 without typing all the 1's. If we store this data set in `assign.dat`, we can use it with the transportation model that we already have:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%writefile assign.dat\n",
        "\n",
        "set ORIG := Coullard Daskin Hazen Hopp Iravani Linetsky\n",
        "\t    Mehrotra Nelson Smilowitz Tamhane White ;\n",
        "set DEST := C118 C138 C140 C246 C250 C251 D237 D239 D241 M233 M239;\n",
        "param supply default 1 ;\n",
        "param demand default 1 ;\n",
        "param cost:\n",
        "\t  C118 C138 C140 C246 C250 C251 D237 D239 D241 M233 M239 :=\n",
        "Coullard    6   9    8    7   11   10    4    5    3    2    1\n",
        "Daskin     11   8    7    6    9   10    1    5    4    2    3\n",
        "Hazen       9  10   11    1    5    6    2    7    8    3    4\n",
        "Hopp       11   9    8   10    6    5    1    7    4    2    3\n",
        "Iravani     3   2    8    9   10   11    1    5    4    6    7\n",
        "Linetsky 11     9   10    5    3    4    6    7    8    1    2\n",
        "Mehrotra    6  11   10    9    8    7    1    2    5    4    3\n",
        "Nelson     11   5    4    6    7    8    1    9   10    2    3\n",
        "Smilowitz 11    9   10    8    6    5    7    3    4    1    2\n",
        "Tamhane     5   6    9    8    4    3    7   10   11    2    1\n",
        "White      11   9    8    4    6    5    3   10    7    2    1 ;"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "reset data;\n",
        "data assign.dat;\n",
        "solve;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "By setting the option `omit_zero_rows` to 1, we can print just the nonzero terms in the objective. This listing tells us each person's assigned room and his or her preference for it:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "%%ampl_eval\n",
        "option omit_zero_rows 1;\n",
        "display {i in ORIG, j in DEST} cost[i,j] * Trans[i,j];"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "It is not hard to see that when all the `supply[i]` and `demand[j]` values are 1, any `Trans[i,j]` satisfying all the constraints must be between 0 and 1. But how did we know that every `Trans[i,j]` would equal either 0 or 1 in the optimal solution, rather than, say, 1/2 ? We were able to rely on a special property of transportation models, which guarantees that as long as all supply and demand values are integers, and all lower and upper bounds on the variables are integers, there will be an optimal solution that is entirely integral. Moreover, we used a solver that always finds one of these integral solutions. But don't let this favorable result mislead you into assuming that integrality can be assured in all other circumstances; even in examples that seem to be much like the transportation model, finding integral solutions can require a special solver, and a lot more work.\n",
        "\n",
        "A problem of assigning 100 people to 100 rooms has ten thousand variables; assigning 1000 people to 1000 rooms yields a million variables. In applications on this scale, however, most of the assignments can be ruled out in advance, so that the number of actual decision variables is not too large. After looking at an initial solution, you may want to rule out some more assignments - in our example, perhaps no assignment to lower than fifth choice should be allowed - or you may want to force some assignments to be made a certain way, in order to see how the rest could be done optimally. These situations require models that can deal with subsets of pairs (of people and offices, or origins and destinations) in a direct way."
      ]
    }
  ],
  "metadata": {
    "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.9.8"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}