{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear programming with Scipy\n",
    "## Dr. Tirthajyoti Sarkar\n",
    "\n",
    "Simple, straight-forward linear programming (LP) problems can also be addressed by Scipy. Prior to 2014, it did not have a LP solver built-in, but it has changed since then. Let’s take a practical factory production problem (borrowed from [this example](https://realpython.com/linear-programming-python/) and slightly changed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## The problem\n",
    "\n",
    "A factory produces four different products, and that the daily produced amount of the first product is $x_1$, the amount produced of the second product is $x_2$, and so on. The goal is to determine the profit-maximizing daily production amount for each product, with the following constraints,\n",
    "\n",
    "- The profit per unit of product is 20, 12, 30, and 15 for the first, second, third, and fourth product, respectively.\n",
    "\n",
    "- Due to manpower constraints, the total number of units produced per day can’t exceed fifty (50).\n",
    "\n",
    "- For each unit of the first product, three units of the raw material A are consumed. Each unit of the second product requires two units of the raw material A and one unit of the raw material B. Each unit of the third product needs two unit of A and five units of B. Finally, each unit of the fourth product requires three units of B.\n",
    "\n",
    "- Due to the transportation and storage constraints, the factory can consume up to one hundred units of the raw material A and ninety units of B per day.\n",
    "\n",
    "The linear programming (LP) problem is,\n",
    "\n",
    "$$\\text{maximize: }\\ 20x_1+12x_2+30x_3+15x_4$$\n",
    "\n",
    "$$\\text{s.t.: } x_1+x_2+x_3+x_4 \\leq 50 \\text { (manpower constraint)}$$\n",
    "\n",
    "$$3x_1+2x_2+2x_3 \\leq 100 \\text { (material A constraint)}$$\n",
    "\n",
    "$$x_2+5x_3+3x_4 \\leq 90 \\text { (material B constraint)}$$\n",
    "\n",
    "$$x_1, x_2, x_3, x_4 \\geq 0$$\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Negative coefficients for the objective function because it is a maximization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "obj = [-20, -12, -30, -15] "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Inequality matrices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# LHS matrix of inequality equations\n",
    "lhs = [[1, 1, 1, 1],\n",
    " [3, 2, 2, 0],\n",
    " [0, 1, 5, 3]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# RHS matrix of inequality equations\n",
    "rhs = [50,\n",
    "      100,\n",
    "      90]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Setup and solve in Scipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.optimize import linprog"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "lp_opt = linprog(c=obj,\n",
    "                 A_ub=lhs,\n",
    "                 b_ub=rhs,\n",
    "                 method = 'interior-point')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "     con: array([], dtype=float64)\n",
       "     fun: -1033.3333113034805\n",
       " message: 'Optimization terminated successfully.'\n",
       "     nit: 4\n",
       "   slack: array([1.06529068e-06, 2.14344466e-06, 1.86209118e-06])\n",
       "  status: 0\n",
       " success: True\n",
       "       x: array([2.66666661e+01, 1.84050438e-08, 9.99999980e+00, 1.33333330e+01])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lp_opt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Note\n",
    "\n",
    "So, the solution says that,\n",
    "\n",
    "- The factory should produce 26.66 units of $x_1$, 10 units of $x_3$, and 13.33 units of $x_4$ every day. The extremely small number corresponding to $x_2$ essentially indicates that no amount of $x_2$ should be produced.\n",
    "\n",
    "- The maximum profit obtainable is $1033.33 under this arrangement.\n",
    "\n",
    "A noteworthy point is that the solution indicates a fractional choice, which may not be feasible in a practical situation. This is the limitation of Scipy solver that it cannot solve the so-called integer programming problems. **Other Python packages like `PuLP`** could be an option for such problems. **[See my article here](https://towardsdatascience.com/linear-programming-and-discrete-optimization-with-python-using-pulp-449f3c5f6e99)**."
   ]
  }
 ],
 "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.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}