05: Transportation_Optimization_Gurobi_CPLEX_PuLP_SciPy_Google_OR_Tools.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/gulabpatel/LinearProgramming/blob/main/05%3A%20Transportation_Optimization_Gurobi_CPLEX_PuLP_SciPy_Google_OR_Tools.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Code walkthrough video : https://www.youtube.com/watch?v=PfPwVKa-tic&t=5059s"
      ],
      "metadata": {
        "id": "CdidvlF3pVMl"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7aCMzxSKBeTf"
      },
      "source": [
        "## Problem Formulation"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hB21oaE6BeTi"
      },
      "source": [
        "The linear programming problem formulation is summarized as below:"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "<img src=\"https://drive.google.com/uc?id=1-XmbE04GLWgHa-WHfwCeH4II1tWNKgQ5\" style=\"width: 100px; height=200px\"/>\n"
      ],
      "metadata": {
        "id": "Y-tHB6YuC22I"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "p1U58YAgBeTj"
      },
      "source": [
        "## Setup Environment"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "cVcS3DQxBeTj"
      },
      "outputs": [],
      "source": [
        "#Install requisite packages\n",
        "!pip install gurobipy\n",
        "!pip install cplex\n",
        "!pip install docplex\n",
        "!pip install PuLP\n",
        "!pip install ortools"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Make sure you \"Restart Runtime\" after installing OR-Tools package for it to be loaded.**"
      ],
      "metadata": {
        "id": "ZnarI5vPG9bC"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "id": "i4ojFGFmBeTm"
      },
      "outputs": [],
      "source": [
        "#Importing Libraries\n",
        "import numpy as np\n",
        "import gurobipy as grb\n",
        "import docplex.mp.model as cpx\n",
        "import pulp as plp\n",
        "from scipy.optimize import linprog\n",
        "from ortools.linear_solver import pywraplp\n",
        "from ortools.init import pywrapinit"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "id": "JxI26j3YBeTm"
      },
      "outputs": [],
      "source": [
        "#Data\n",
        "supply = {'A':70,'B':50,'C':30}\n",
        "demand = {'D':30,'E':24,'F':12,'G':42,'H':6}\n",
        "cost_arr = np.array([[16,7,17,14,19],\n",
        "                    [9,11,16,10,5],\n",
        "                    [10,18,6,13,8]])"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "id": "lSHg88OnBeTn",
        "outputId": "b9fe1d18-68f8-47bd-c624-4f9593028cd1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {},
          "execution_count": 4
        }
      ],
      "source": [
        "#Check if cost array is of right shape\n",
        "cost_arr.shape == (len(supply), len(demand))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QM5UbP1eBeTn"
      },
      "source": [
        "## Gurobi Implementation"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TyALI1vcBeTo"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>1. Initializing Model</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "id": "XnHIDdFwBeTo",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "5e18c8af-863b-4d2e-89ca-bf64cd4910c4"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Restricted license - for non-production use only - expires 2023-10-25\n"
          ]
        }
      ],
      "source": [
        "gurobi_lp_model = grb.Model()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PcPWFSZVBeTp"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>2. Define Decision Variables</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "id": "7UDiEcFQBeTp",
        "outputId": "4fa9f2c1-a9df-471e-bced-40ac7e533f14",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{(0, 0): <gurobi.Var *Awaiting Model Update*>,\n",
              " (0, 1): <gurobi.Var *Awaiting Model Update*>,\n",
              " (0, 2): <gurobi.Var *Awaiting Model Update*>,\n",
              " (0, 3): <gurobi.Var *Awaiting Model Update*>,\n",
              " (0, 4): <gurobi.Var *Awaiting Model Update*>,\n",
              " (1, 0): <gurobi.Var *Awaiting Model Update*>,\n",
              " (1, 1): <gurobi.Var *Awaiting Model Update*>,\n",
              " (1, 2): <gurobi.Var *Awaiting Model Update*>,\n",
              " (1, 3): <gurobi.Var *Awaiting Model Update*>,\n",
              " (1, 4): <gurobi.Var *Awaiting Model Update*>,\n",
              " (2, 0): <gurobi.Var *Awaiting Model Update*>,\n",
              " (2, 1): <gurobi.Var *Awaiting Model Update*>,\n",
              " (2, 2): <gurobi.Var *Awaiting Model Update*>,\n",
              " (2, 3): <gurobi.Var *Awaiting Model Update*>,\n",
              " (2, 4): <gurobi.Var *Awaiting Model Update*>}"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ],
      "source": [
        "quantity_arr  = {(i,j): gurobi_lp_model.addVar(vtype = grb.GRB.INTEGER, name=\"%s-%s\"%(list(supply.keys())[i],list(demand.keys())[j])) for i in range(len(supply)) for j in range(len(demand))}\n",
        "quantity_arr"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3Bzn3vA8BeTp"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>3. Constraints</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NPlvuQRSBeTq"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(i) Supply Constraint</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {
        "id": "cHu8gjdRBeTq"
      },
      "outputs": [],
      "source": [
        "for i in range(len(supply)):\n",
        "    gurobi_lp_model.addConstr(sum(quantity_arr[(i,j)] for j in range(len(demand))) <= list(supply.values())[i])\n",
        "    "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yuORXlZZBeTq"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(ii) Demand Constraint</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {
        "id": "BMfR5oCsBeTr"
      },
      "outputs": [],
      "source": [
        "for j in range(len(demand)):\n",
        "    gurobi_lp_model.addConstr(sum(quantity_arr[(i,j)] for i in range(len(supply))) >= list(demand.values())[j])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NCMZHch5BeTr"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(iii) Non-Negativity Constraint</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {
        "id": "5LfQj345BeTr"
      },
      "outputs": [],
      "source": [
        "for i in range(len(supply)):\n",
        "    for j in range(len(demand)):\n",
        "        gurobi_lp_model.addConstr(quantity_arr[(i,j)] >= 0)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "chU56NenBeTr"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>4. Objective Function</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {
        "id": "aDMrzGz7BeTs"
      },
      "outputs": [],
      "source": [
        "gurobi_lp_model.setObjective(sum(cost_arr[i][j]*quantity_arr[(i,j)] for i in range(len(supply)) for j in range(len(demand))), grb.GRB.MINIMIZE)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6aKqhre_BeTs"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>5. Solve Problem</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "metadata": {
        "id": "QzaOacpfBeTs",
        "outputId": "35e0c35c-c3a1-4df0-c290-3a88aa92c147",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (linux64)\n",
            "Thread count: 1 physical cores, 2 logical processors, using up to 2 threads\n",
            "Optimize a model with 23 rows, 15 columns and 45 nonzeros\n",
            "Model fingerprint: 0x4f2602a0\n",
            "Variable types: 0 continuous, 15 integer (0 binary)\n",
            "Coefficient statistics:\n",
            "  Matrix range     [1e+00, 1e+00]\n",
            "  Objective range  [5e+00, 2e+01]\n",
            "  Bounds range     [0e+00, 0e+00]\n",
            "  RHS range        [6e+00, 7e+01]\n",
            "Found heuristic solution: objective 1210.0000000\n",
            "Presolve removed 15 rows and 0 columns\n",
            "Presolve time: 0.00s\n",
            "Presolved: 8 rows, 15 columns, 30 nonzeros\n",
            "Variable types: 0 continuous, 15 integer (0 binary)\n",
            "\n",
            "Root relaxation: objective 1.018000e+03, 7 iterations, 0.00 seconds (0.00 work units)\n",
            "\n",
            "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
            " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
            "\n",
            "*    0     0               0    1018.0000000 1018.00000  0.00%     -    0s\n",
            "\n",
            "Explored 1 nodes (7 simplex iterations) in 0.04 seconds (0.00 work units)\n",
            "Thread count was 2 (of 2 available processors)\n",
            "\n",
            "Solution count 2: 1018 1210 \n",
            "\n",
            "Optimal solution found (tolerance 1.00e-04)\n",
            "Best objective 1.018000000000e+03, best bound 1.018000000000e+03, gap 0.0000%\n"
          ]
        }
      ],
      "source": [
        "gurobi_lp_model.optimize()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8mddq6hnBeTs"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>6. Results</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 12,
      "metadata": {
        "id": "i2ZbQl13BeTt",
        "outputId": "0015eda9-09a1-4608-a179-52f103eab3e7",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{(0, 0): <gurobi.Var A-D (value -0.0)>,\n",
              " (0, 1): <gurobi.Var A-E (value 24.0)>,\n",
              " (0, 2): <gurobi.Var A-F (value -0.0)>,\n",
              " (0, 3): <gurobi.Var A-G (value 10.0)>,\n",
              " (0, 4): <gurobi.Var A-H (value -0.0)>,\n",
              " (1, 0): <gurobi.Var B-D (value 12.0)>,\n",
              " (1, 1): <gurobi.Var B-E (value -0.0)>,\n",
              " (1, 2): <gurobi.Var B-F (value -0.0)>,\n",
              " (1, 3): <gurobi.Var B-G (value 32.0)>,\n",
              " (1, 4): <gurobi.Var B-H (value 6.0)>,\n",
              " (2, 0): <gurobi.Var C-D (value 18.0)>,\n",
              " (2, 1): <gurobi.Var C-E (value -0.0)>,\n",
              " (2, 2): <gurobi.Var C-F (value 12.0)>,\n",
              " (2, 3): <gurobi.Var C-G (value -0.0)>,\n",
              " (2, 4): <gurobi.Var C-H (value -0.0)>}"
            ]
          },
          "metadata": {},
          "execution_count": 12
        }
      ],
      "source": [
        "quantity_arr"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 13,
      "metadata": {
        "id": "TArxucerBeTt",
        "outputId": "730809c8-434a-4e72-8e37-93073d4b2467",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Optimal shipments from supply city A to demand city D is 0\n",
            "Optimal shipments from supply city A to demand city E is 24\n",
            "Optimal shipments from supply city A to demand city F is 0\n",
            "Optimal shipments from supply city A to demand city G is 10\n",
            "Optimal shipments from supply city A to demand city H is 0\n",
            "Optimal shipments from supply city B to demand city D is 12\n",
            "Optimal shipments from supply city B to demand city E is 0\n",
            "Optimal shipments from supply city B to demand city F is 0\n",
            "Optimal shipments from supply city B to demand city G is 32\n",
            "Optimal shipments from supply city B to demand city H is 6\n",
            "Optimal shipments from supply city C to demand city D is 18\n",
            "Optimal shipments from supply city C to demand city E is 0\n",
            "Optimal shipments from supply city C to demand city F is 12\n",
            "Optimal shipments from supply city C to demand city G is 0\n",
            "Optimal shipments from supply city C to demand city H is 0\n",
            "Total minimum shipping cost is 1018\n"
          ]
        }
      ],
      "source": [
        "# This prints out the optimal value for all the decision variables\n",
        "for i in range(len(supply)):\n",
        "    for j in range(len(demand)):\n",
        "        print(\"Optimal shipments from supply city %s to demand city %s is %d\"%(list(supply.keys())[i], list(demand.keys())[j], quantity_arr[(i,j)].x))\n",
        "# This gives the objective value that we were trying to maximize.\n",
        "print(\"Total minimum shipping cost is %d\"%gurobi_lp_model.objval)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MXjRQEJMBeTt"
      },
      "source": [
        "## CPLEX Implementation"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hd_O0G6DBeTt"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>1. Initializing Model</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 14,
      "metadata": {
        "id": "rdrFTUWuBeTt"
      },
      "outputs": [],
      "source": [
        "cplex_lp_model = cpx.Model()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "D9_n4eRpBeTu"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>2. Define Decision Variables</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 15,
      "metadata": {
        "id": "kjRGEA0MBeTu",
        "outputId": "f106a65a-b1bb-4d6b-ecfe-60bc7471ed5a",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{(0, 0): docplex.mp.Var(type=I,name='A-D'),\n",
              " (0, 1): docplex.mp.Var(type=I,name='A-E'),\n",
              " (0, 2): docplex.mp.Var(type=I,name='A-F'),\n",
              " (0, 3): docplex.mp.Var(type=I,name='A-G'),\n",
              " (0, 4): docplex.mp.Var(type=I,name='A-H'),\n",
              " (1, 0): docplex.mp.Var(type=I,name='B-D'),\n",
              " (1, 1): docplex.mp.Var(type=I,name='B-E'),\n",
              " (1, 2): docplex.mp.Var(type=I,name='B-F'),\n",
              " (1, 3): docplex.mp.Var(type=I,name='B-G'),\n",
              " (1, 4): docplex.mp.Var(type=I,name='B-H'),\n",
              " (2, 0): docplex.mp.Var(type=I,name='C-D'),\n",
              " (2, 1): docplex.mp.Var(type=I,name='C-E'),\n",
              " (2, 2): docplex.mp.Var(type=I,name='C-F'),\n",
              " (2, 3): docplex.mp.Var(type=I,name='C-G'),\n",
              " (2, 4): docplex.mp.Var(type=I,name='C-H')}"
            ]
          },
          "metadata": {},
          "execution_count": 15
        }
      ],
      "source": [
        "quantity_arr  = {(i,j): cplex_lp_model.integer_var(name=\"%s-%s\"%(list(supply.keys())[i],list(demand.keys())[j])) for i in range(len(supply)) for j in range(len(demand))}\n",
        "quantity_arr"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "plKxxVpaBeTu"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>3. Constraints</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vFGOZrrfBeTu"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(i) Supply Constraint</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 16,
      "metadata": {
        "id": "OM9nveqwBeTu"
      },
      "outputs": [],
      "source": [
        "supply_constraints = {i : cplex_lp_model.add_constraint(ct=cplex_lp_model.sum(quantity_arr[(i,j)] for j in range(len(demand))) <= list(supply.values())[i]) for i in range(len(supply))}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JjdlyNoPBeTu"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(ii) Demand Constraint</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 17,
      "metadata": {
        "id": "daC8RKtUBeTv"
      },
      "outputs": [],
      "source": [
        "demand_constraints = {i : cplex_lp_model.add_constraint(ct=cplex_lp_model.sum(quantity_arr[(i,j)] for i in range(len(supply))) >= list(demand.values())[j]) for j in range(len(demand))}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "w73z4k3eBeTw"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(iii) Non-Negativity Constraint</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 18,
      "metadata": {
        "id": "mQ236j57BeTw"
      },
      "outputs": [],
      "source": [
        "non_neg_constraints = {(i,j): cplex_lp_model.add_constraint(ct=quantity_arr[(i,j)] >= 0) for i in range(len(supply)) for j in range(len(demand))}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EURSzrXvBeTw"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>4. Objective Function</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 19,
      "metadata": {
        "id": "shgY9LmaBeTw"
      },
      "outputs": [],
      "source": [
        "objective = cplex_lp_model.sum(cost_arr[i][j]*quantity_arr[(i,j)] for i in range(len(supply)) for j in range(len(demand)))\n",
        "cplex_lp_model.minimize(objective)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sjg_UNhjBeTw"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>5. Solve Problem</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 20,
      "metadata": {
        "id": "cd0De72nBeTw",
        "outputId": "2068b891-c63f-4c7e-fac1-782d8b5a63c9",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "docplex.mp.solution.SolveSolution(obj=1018,values={A-E:24,A-G:10,B-D:12,.."
            ]
          },
          "metadata": {},
          "execution_count": 20
        }
      ],
      "source": [
        "cplex_lp_model.solve()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BMQ5LynaBeTx"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>6. Results</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 21,
      "metadata": {
        "id": "-J0RaX5IBeTx",
        "outputId": "fd8e98c1-f291-4205-8dc9-a0cf0b755520",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Optimal shipments from supply city A to demand city D is 0\n",
            "Optimal shipments from supply city A to demand city E is 24\n",
            "Optimal shipments from supply city A to demand city F is 0\n",
            "Optimal shipments from supply city A to demand city G is 10\n",
            "Optimal shipments from supply city A to demand city H is 0\n",
            "Optimal shipments from supply city B to demand city D is 12\n",
            "Optimal shipments from supply city B to demand city E is 0\n",
            "Optimal shipments from supply city B to demand city F is 0\n",
            "Optimal shipments from supply city B to demand city G is 32\n",
            "Optimal shipments from supply city B to demand city H is 6\n",
            "Optimal shipments from supply city C to demand city D is 18\n",
            "Optimal shipments from supply city C to demand city E is 0\n",
            "Optimal shipments from supply city C to demand city F is 12\n",
            "Optimal shipments from supply city C to demand city G is 0\n",
            "Optimal shipments from supply city C to demand city H is 0\n",
            "Total minimum shipping cost is 1018\n"
          ]
        }
      ],
      "source": [
        "# This prints out the optimal value for all the decision variables\n",
        "for i in range(len(supply)):\n",
        "    for j in range(len(demand)):\n",
        "        print(\"Optimal shipments from supply city %s to demand city %s is %d\"%(list(supply.keys())[i], list(demand.keys())[j], quantity_arr[(i,j)].solution_value))\n",
        "# This gives the objective value that we were trying to maximize.\n",
        "print(\"Total minimum shipping cost is %d\"%cplex_lp_model.objective_value)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hhhFkn6cBeTx"
      },
      "source": [
        "## PuLP Implementation"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6J4zM6VjBeTx"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>1. Initializing Model</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 22,
      "metadata": {
        "id": "Ov-uZXrGBeTx"
      },
      "outputs": [],
      "source": [
        "pulp_lp_model = plp.LpProblem()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KPqKJHUsBeTy"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>2. Define Decision Variables</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 23,
      "metadata": {
        "id": "RJDsVP5UBeTy",
        "outputId": "e98790dd-beb2-4bdc-d9e2-11c426d22d3a",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{(0, 0): A_D,\n",
              " (0, 1): A_E,\n",
              " (0, 2): A_F,\n",
              " (0, 3): A_G,\n",
              " (0, 4): A_H,\n",
              " (1, 0): B_D,\n",
              " (1, 1): B_E,\n",
              " (1, 2): B_F,\n",
              " (1, 3): B_G,\n",
              " (1, 4): B_H,\n",
              " (2, 0): C_D,\n",
              " (2, 1): C_E,\n",
              " (2, 2): C_F,\n",
              " (2, 3): C_G,\n",
              " (2, 4): C_H}"
            ]
          },
          "metadata": {},
          "execution_count": 23
        }
      ],
      "source": [
        "quantity_arr  = {(i,j): plp.LpVariable(cat=plp.LpInteger, name=\"%s-%s\"%(list(supply.keys())[i],list(demand.keys())[j])) for i in range(len(supply)) for j in range(len(demand))}\n",
        "quantity_arr"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "x8H-GAvkBeTy"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>3. Constraints</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0srWclF2BeTy"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(i) Supply Constraint</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 24,
      "metadata": {
        "id": "3QIfuwERBeTy"
      },
      "outputs": [],
      "source": [
        "supply_constraints = {i : pulp_lp_model.addConstraint(\n",
        "plp.LpConstraint(\n",
        "             e=plp.lpSum(quantity_arr[(i,j)] for j in range(len(demand))),\n",
        "             sense=plp.LpConstraintLE,\n",
        "             rhs=list(supply.values())[i],\n",
        "             name=\"supply_constraint_%s\"%(list(supply.keys())[i])))\n",
        "       for i in range(len(supply))}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LXxsWf3mBeTy"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(ii) Demand Constraint</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 25,
      "metadata": {
        "id": "zLytl3L-BeTz"
      },
      "outputs": [],
      "source": [
        "demand_constraints = {j : pulp_lp_model.addConstraint(\n",
        "plp.LpConstraint(\n",
        "             e=plp.lpSum(quantity_arr[(i,j)] for i in range(len(supply))),\n",
        "             sense=plp.LpConstraintGE,\n",
        "             rhs=list(demand.values())[j],\n",
        "             name=\"demand_constraint_%s\"%(list(demand.keys())[j])))\n",
        "       for j in range(len(demand))}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bG_9JGsaBeTz"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(iii) Non-Negativity Constraint</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 26,
      "metadata": {
        "id": "TdOW4e2oBeTz"
      },
      "outputs": [],
      "source": [
        "non_neg_constraints = {(i,j): pulp_lp_model.addConstraint(\n",
        "plp.LpConstraint(\n",
        "             e=quantity_arr[(i,j)],\n",
        "             sense=plp.LpConstraintGE,\n",
        "             rhs=0,\n",
        "             name=\"non_neg_constraint_{0}_{1}\".format(i,j)))\n",
        "        for i in range(len(supply)) for j in range(len(demand))}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SSS9A5fUBeTz"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>4. Objective Function</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 27,
      "metadata": {
        "id": "NdNFc8w3BeTz"
      },
      "outputs": [],
      "source": [
        "objective = plp.lpSum(cost_arr[i][j]*quantity_arr[(i,j)] for i in range(len(supply)) for j in range(len(demand)))\n",
        "pulp_lp_model.sense = plp.LpMinimize\n",
        "pulp_lp_model.setObjective(objective)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IKxfnZcdBeTz"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>5. Solve Problem</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 28,
      "metadata": {
        "id": "Jw3MRcJ0BeTz"
      },
      "outputs": [],
      "source": [
        "status = pulp_lp_model.solve()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-xiLrSVaBeT0"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>6. Results</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 29,
      "metadata": {
        "id": "3jwPnEe3BeT0",
        "outputId": "dd24d8be-87d9-477d-ce1c-2b74cfd9d2ec",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Optimal shipments from supply city A to demand city D is 0\n",
            "Optimal shipments from supply city A to demand city E is 24\n",
            "Optimal shipments from supply city A to demand city F is 0\n",
            "Optimal shipments from supply city A to demand city G is 10\n",
            "Optimal shipments from supply city A to demand city H is 0\n",
            "Optimal shipments from supply city B to demand city D is 12\n",
            "Optimal shipments from supply city B to demand city E is 0\n",
            "Optimal shipments from supply city B to demand city F is 0\n",
            "Optimal shipments from supply city B to demand city G is 32\n",
            "Optimal shipments from supply city B to demand city H is 6\n",
            "Optimal shipments from supply city C to demand city D is 18\n",
            "Optimal shipments from supply city C to demand city E is 0\n",
            "Optimal shipments from supply city C to demand city F is 12\n",
            "Optimal shipments from supply city C to demand city G is 0\n",
            "Optimal shipments from supply city C to demand city H is 0\n",
            "Total minimum shipping cost is 1018\n"
          ]
        }
      ],
      "source": [
        "# This prints out the optimal value for all the decision variables\n",
        "for i in range(len(supply)):\n",
        "    for j in range(len(demand)):\n",
        "        print(\"Optimal shipments from supply city %s to demand city %s is %d\"%(list(supply.keys())[i], list(demand.keys())[j], quantity_arr[(i,j)].varValue))\n",
        "# This gives the objective value that we were trying to maximize.\n",
        "print(\"Total minimum shipping cost is %d\"%pulp_lp_model.objective.value())"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PxKP5GXGBeT0"
      },
      "source": [
        "## SciPy Implementation"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "e9JZ5pehBeT0"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>1. Constraints</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "znRzbvmcBeT0"
      },
      "source": [
        "**Order of Variables Considered - [AD,AE,AF,AG,AH,BD,BE,BF,BG,BH,CD,CE,CF,CG,CH]**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qQuZ_8rjBeT0"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(i) Supply Constraint</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 30,
      "metadata": {
        "id": "5N2WMg0RBeT0",
        "outputId": "2e31c946-d45f-4c4e-a0ae-4fb2d8d5d7f9",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[1 1 1 1 1 0 0 0 0 0 0 0 0 0 0]\n",
            " [0 0 0 0 0 1 1 1 1 1 0 0 0 0 0]\n",
            " [0 0 0 0 0 0 0 0 0 0 1 1 1 1 1]] \n",
            " [70 50 30]\n"
          ]
        }
      ],
      "source": [
        "supply_constraints_lhs = np.array([[1]*len(demand) + [0]*len(demand) + [0]*len(demand), \\\n",
        "                                   [0]*len(demand) + [1]*len(demand) + [0]*len(demand), \n",
        "                                   [0]*len(demand) + [0]*len(demand) + [1]*len(demand)])\n",
        "supply_constraints_rhs = np.array(list(supply.values()))\n",
        "print(supply_constraints_lhs, '\\n', supply_constraints_rhs)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "J5UdKTCmBeT2"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(ii) Demand Constraint</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 31,
      "metadata": {
        "id": "rOMK9IxxBeT2",
        "outputId": "8360053e-b2c4-444a-ab5c-ae69dac27003",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[-1  0  0  0  0 -1  0  0  0  0 -1  0  0  0  0]\n",
            " [ 0 -1  0  0  0  0 -1  0  0  0  0 -1  0  0  0]\n",
            " [ 0  0 -1  0  0  0  0 -1  0  0  0  0 -1  0  0]\n",
            " [ 0  0  0 -1  0  0  0  0 -1  0  0  0  0 -1  0]\n",
            " [ 0  0  0  0 -1  0  0  0  0 -1  0  0  0  0 -1]] \n",
            " [-30 -24 -12 -42  -6]\n"
          ]
        }
      ],
      "source": [
        "demand_constraints_lhs = np.array([np.ndarray.flatten(np.array([-1]*len(supply)+ [0]*len(supply)*4).reshape(5,3).T), \\\n",
        "                                   np.ndarray.flatten(np.array([0]*len(supply) + [-1]*len(supply) + [0]*len(supply)*3).reshape(5,3).T), \\\n",
        "                                   np.ndarray.flatten(np.array([0]*len(supply)*2 + [-1]*len(supply) + [0]*len(supply)*2).reshape(5,3).T), \\\n",
        "                                   np.ndarray.flatten(np.array([0]*len(supply)*3 + [-1]*len(supply) + [0]*len(supply)*1).reshape(5,3).T), \\\n",
        "                                   np.ndarray.flatten(np.array([0]*len(supply)*4 + [-1]*len(supply)).reshape(5,3).T)])\n",
        "demand_constraints_rhs = np.array([val*(-1) for val in list(demand.values())])\n",
        "print(demand_constraints_lhs, '\\n', demand_constraints_rhs)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_xaQLjifBeT2"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(iii) Non-Negativity Constraint</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 32,
      "metadata": {
        "id": "gL89bIh-BeT2"
      },
      "outputs": [],
      "source": [
        "non_neg_constraints_lhs = np.diag(np.full(len(supply)*len(demand),-1))\n",
        "non_neg_constraints_rhs = np.array([0]*len(supply)*len(demand))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dt8ftN2eBeT2"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h4 style='margin:10px 5px'>(iv) All Constraints</h4>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 33,
      "metadata": {
        "id": "fnZYt9p0BeT2",
        "outputId": "31317330-5674-45aa-99df-24bd474cdb21",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[ 1  1  1  1  1  0  0  0  0  0  0  0  0  0  0]\n",
            " [ 0  0  0  0  0  1  1  1  1  1  0  0  0  0  0]\n",
            " [ 0  0  0  0  0  0  0  0  0  0  1  1  1  1  1]\n",
            " [-1  0  0  0  0 -1  0  0  0  0 -1  0  0  0  0]\n",
            " [ 0 -1  0  0  0  0 -1  0  0  0  0 -1  0  0  0]\n",
            " [ 0  0 -1  0  0  0  0 -1  0  0  0  0 -1  0  0]\n",
            " [ 0  0  0 -1  0  0  0  0 -1  0  0  0  0 -1  0]\n",
            " [ 0  0  0  0 -1  0  0  0  0 -1  0  0  0  0 -1]\n",
            " [-1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]\n",
            " [ 0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0]\n",
            " [ 0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0]\n",
            " [ 0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0]\n",
            " [ 0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0]\n",
            " [ 0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0]\n",
            " [ 0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0]\n",
            " [ 0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0]\n",
            " [ 0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0]\n",
            " [ 0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0]\n",
            " [ 0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0]\n",
            " [ 0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0]\n",
            " [ 0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0]\n",
            " [ 0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0]\n",
            " [ 0  0  0  0  0  0  0  0  0  0  0  0  0  0 -1]] \n",
            "\n",
            " [ 70  50  30 -30 -24 -12 -42  -6   0   0   0   0   0   0   0   0   0   0\n",
            "   0   0   0   0   0]\n"
          ]
        }
      ],
      "source": [
        "all_constraints_lhs = np.concatenate((supply_constraints_lhs,demand_constraints_lhs,non_neg_constraints_lhs),axis=0)\n",
        "all_constraints_rhs = np.concatenate((supply_constraints_rhs, demand_constraints_rhs,non_neg_constraints_rhs))\n",
        "print(all_constraints_lhs, '\\n\\n', all_constraints_rhs)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LS4Th1OFBeT3"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>2. Objective Function</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 34,
      "metadata": {
        "id": "DG0JgPHfBeT3",
        "outputId": "b762c887-1389-4933-b73c-506ee155c912",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([16,  7, 17, 14, 19,  9, 11, 16, 10,  5, 10, 18,  6, 13,  8])"
            ]
          },
          "metadata": {},
          "execution_count": 34
        }
      ],
      "source": [
        "obj = np.ndarray.flatten(cost_arr)\n",
        "obj"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ALh0pQfNBeT3"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>3. Solve Problem</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 35,
      "metadata": {
        "id": "-FGPYVrTBeT3"
      },
      "outputs": [],
      "source": [
        "quantity_arr = linprog(obj, A_ub=all_constraints_lhs, b_ub=all_constraints_rhs, method=\"simplex\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3LgE1XCkBeT3"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>4. Results</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 36,
      "metadata": {
        "id": "M9gl_NlGBeT3",
        "outputId": "e748e4a6-056e-4cac-b343-7b9e714382ed",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Optimal shipments from supply city A to demand city D is 0\n",
            "Optimal shipments from supply city A to demand city E is 24\n",
            "Optimal shipments from supply city A to demand city F is 0\n",
            "Optimal shipments from supply city A to demand city G is 10\n",
            "Optimal shipments from supply city A to demand city H is 0\n",
            "Optimal shipments from supply city B to demand city D is 12\n",
            "Optimal shipments from supply city B to demand city E is 0\n",
            "Optimal shipments from supply city B to demand city F is 0\n",
            "Optimal shipments from supply city B to demand city G is 32\n",
            "Optimal shipments from supply city B to demand city H is 6\n",
            "Optimal shipments from supply city C to demand city D is 18\n",
            "Optimal shipments from supply city C to demand city E is 0\n",
            "Optimal shipments from supply city C to demand city F is 12\n",
            "Optimal shipments from supply city C to demand city G is 0\n",
            "Optimal shipments from supply city C to demand city H is 0\n",
            "Total minimum shipping cost is 1018\n"
          ]
        }
      ],
      "source": [
        "# This prints out the optimal value for all the decision variables\n",
        "for i in range(len(supply)):\n",
        "    for j in range(len(demand)):\n",
        "        print(\"Optimal shipments from supply city %s to demand city %s is %d\"%(list(supply.keys())[i], list(demand.keys())[j], quantity_arr.x[len(demand)*i+j]))\n",
        "# This gives the objective value that we were trying to maximize.\n",
        "print(\"Total minimum shipping cost is %d\"%quantity_arr.fun)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yy9tWg7HBeT3"
      },
      "source": [
        "## Google OR Tools Implementation"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PfL9jqKMBeT4"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>1. Initializing Model</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 37,
      "metadata": {
        "id": "-eIhkUPcBeT4"
      },
      "outputs": [],
      "source": [
        "#Storing Data\n",
        "data = {}\n",
        "data['constraint_coef'] = all_constraints_lhs\n",
        "data['bounds'] = all_constraints_rhs\n",
        "data['obj_coef'] = obj\n",
        "data['num_var'] = len(supply)*len(demand)\n",
        "data['num_constraint'] = len(supply) + len(demand) + len(supply)*len(demand)\n",
        "\n",
        "ortools_lp_model = pywraplp.Solver.CreateSolver('SCIP')"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VAjkGkHsBeT4"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>2. Define Decision Variables</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 38,
      "metadata": {
        "id": "Yk9D6dViBeT4",
        "outputId": "2f1e9b1a-6e43-4b92-ac82-f3b8197f927e",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Number of variables = 15\n"
          ]
        }
      ],
      "source": [
        "infinity = ortools_lp_model.infinity()\n",
        "quantity_arr = {}\n",
        "for p in range(data['num_var']):\n",
        "    quantity_arr[p] = ortools_lp_model.IntVar(0, infinity, 'quantity_arr[%i]' % p)\n",
        "print('Number of variables =', ortools_lp_model.NumVariables())"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "URT7E4ctBeT4"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>3. Constraints</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 39,
      "metadata": {
        "id": "O2tx0ChbBeT4",
        "outputId": "fbd6d5c3-b875-48eb-e30c-2f9ff1f8b234",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Number of constraints = 23\n"
          ]
        }
      ],
      "source": [
        "for q in range(data['num_constraint']):\n",
        "     constraint_expr = [data['constraint_coef'][q][r] * quantity_arr[r] for r in range(data['num_var'])]\n",
        "     ortools_lp_model.Add(sum(constraint_expr) <= data['bounds'][q])\n",
        "print('Number of constraints =', ortools_lp_model.NumConstraints())"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XGkIupxVBeT4"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>4. Objective Function</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 40,
      "metadata": {
        "id": "l7xXZE9qBeT4"
      },
      "outputs": [],
      "source": [
        "obj_expr = [data['obj_coef'][s] * quantity_arr[s] for s in range(data['num_var'])]\n",
        "ortools_lp_model.Minimize(ortools_lp_model.Sum(obj_expr))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qtud2p5wBeT5"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>5. Solve Problem</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 41,
      "metadata": {
        "id": "K0GqTDTkBeT5"
      },
      "outputs": [],
      "source": [
        "status = ortools_lp_model.Solve()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "i6XMv4qJBeT5"
      },
      "source": [
        "<div class=\"alert alert-info\" style=\"background-color:#006a79; color:white; padding:0px 10px; border-radius:5px;\"><h2 style='margin:10px 5px'>6. Results</h2>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 42,
      "metadata": {
        "id": "mcUKF1WqBeT5",
        "outputId": "6719001c-6141-4acd-9945-320452ee006b",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Optimal shipments from supply city A to demand city D is 0\n",
            "Optimal shipments from supply city A to demand city E is 24\n",
            "Optimal shipments from supply city A to demand city F is 0\n",
            "Optimal shipments from supply city A to demand city G is 10\n",
            "Optimal shipments from supply city A to demand city H is 0\n",
            "Optimal shipments from supply city B to demand city D is 12\n",
            "Optimal shipments from supply city B to demand city E is 0\n",
            "Optimal shipments from supply city B to demand city F is 0\n",
            "Optimal shipments from supply city B to demand city G is 32\n",
            "Optimal shipments from supply city B to demand city H is 6\n",
            "Optimal shipments from supply city C to demand city D is 18\n",
            "Optimal shipments from supply city C to demand city E is 0\n",
            "Optimal shipments from supply city C to demand city F is 12\n",
            "Optimal shipments from supply city C to demand city G is 0\n",
            "Optimal shipments from supply city C to demand city H is 0\n",
            "Total minimum shipping cost is 1018\n"
          ]
        }
      ],
      "source": [
        "# This prints out the optimal value for all the decision variables\n",
        "for i in range(len(supply)):\n",
        "    for j in range(len(demand)):\n",
        "        print(\"Optimal shipments from supply city %s to demand city %s is %d\"%(list(supply.keys())[i], list(demand.keys())[j], quantity_arr[len(demand)*i+j].solution_value()))\n",
        "# This gives the objective value that we were trying to maximize.\n",
        "print(\"Total minimum shipping cost is %d\"%round(ortools_lp_model.Objective().Value()))"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "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.8.3"
    },
    "colab": {
      "name": "05: Transportation_Optimization_Gurobi_CPLEX_PuLP_SciPy_Google-OR-Tools.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "7aCMzxSKBeTf",
        "p1U58YAgBeTj",
        "QM5UbP1eBeTn",
        "MXjRQEJMBeTt",
        "hhhFkn6cBeTx",
        "PxKP5GXGBeT0",
        "yy9tWg7HBeT3"
      ],
      "toc_visible": true,
      "include_colab_link": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}