{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PuLPを使ってみる"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "特に実装すべきアルゴリズムはなかったが、せっかくなのでpythonで線形計画問題を解くためのパッケージ(?)である**PuLP**を使って実際に線形計画問題を解く方法を調べてみた。\n",
    "\n",
    "[参考にしたサイト](http://qiita.com/Tsutomu-KKE@github/items/070ca9cb37c6b2b492f0)\n",
    "\n",
    "インストール方法は、\n",
    "```\n",
    "sudo pip install pulp\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pulp import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\max 100x + 100y$$\n",
    "\n",
    "$$ s.t. \\\\ x + 2y \\leq 16 $$\n",
    "\n",
    "$$ x + y \\leq 18 $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.0 6.0\n"
     ]
    }
   ],
   "source": [
    "m = LpProblem(sense=LpMaximize) # 数理モデル\n",
    "x = LpVariable('x', lowBound=0) # 変数\n",
    "y = LpVariable('y', lowBound=0)\n",
    "m += 100 * x + 100 * y # 目的関数\n",
    "m += x + 2 * y <= 16 #制約1\n",
    "m += 3 * x + y <= 18 # 制約2\n",
    "m.solve() # ソルバー実行\n",
    "print(value(x), value(y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100*x + 100*y\n"
     ]
    }
   ],
   "source": [
    "print(m.objective)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000.0\n"
     ]
    }
   ],
   "source": [
    "print(value(m.objective))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "status = m.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal\n"
     ]
    }
   ],
   "source": [
    "print (LpStatus[status])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PuLP with pandas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "輸送最適化問題を解く（参考サイトに問題の詳細あり）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np, pandas as pd\n",
    "from itertools import product\n",
    "from pulp import *\n",
    "\n",
    "np.random.seed(1)\n",
    "nw, nf = 3, 4\n",
    "pr = list(product(range(nw),range(nf)))\n",
    "supply = np.random.randint(30, 50, nw)\n",
    "demand = np.random.randint(20, 40, nf)\n",
    "cost = np.random.randint(10, 20, (nw,nf))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(0, 0): 28.0,\n",
       " (0, 1): 7.0,\n",
       " (1, 2): 31.0,\n",
       " (1, 3): 5.0,\n",
       " (2, 1): 22.0,\n",
       " (2, 3): 20.0}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# pandasを使わずにモデリングすると\n",
    "\n",
    "m1 = LpProblem() # minimizing\n",
    "v1 = {(i,j):LpVariable('v%d_%d'%(i,j), lowBound=0) for i,j in pr}\n",
    "m1 += lpSum(cost[i][j] * v1[i,j] for i,j in pr) # objective function\n",
    "for i in range(nw):\n",
    "    m1 += lpSum(v1[i,j] for j in range(nf)) <= supply[i]\n",
    "for j in range(nf):\n",
    "    m1 += lpSum(v1[i,j] for i in range(nw)) >= demand[j]\n",
    "m1.solve()\n",
    "{k:value(x) for k,x in v1.items() if value(x) > 0}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(0, 0): v0_0,\n",
       " (0, 1): v0_1,\n",
       " (0, 2): v0_2,\n",
       " (0, 3): v0_3,\n",
       " (1, 0): v1_0,\n",
       " (1, 1): v1_1,\n",
       " (1, 2): v1_2,\n",
       " (1, 3): v1_3,\n",
       " (2, 0): v2_0,\n",
       " (2, 1): v2_1,\n",
       " (2, 2): v2_2,\n",
       " (2, 3): v2_3}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "v1_1"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v1[1,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_items([((0, 1), v0_1), ((1, 2), v1_2), ((0, 0), v0_0), ((1, 1), v1_1), ((2, 1), v2_1), ((0, 2), v0_2), ((2, 0), v2_0), ((1, 3), v1_3), ((2, 3), v2_3), ((2, 2), v2_2), ((1, 0), v1_0), ((0, 3), v0_3)])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v1.items()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value(v1[1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>warehouse</th>\n",
       "      <th>factory</th>\n",
       "      <th>cost</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>11</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   warehouse  factory  cost\n",
       "0          0        0    10\n",
       "1          0        1    10\n",
       "2          0        2    11"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# pandasを使ってモデリング\n",
    "a = pd.DataFrame([(i,j) for i, j in pr], columns=['warehouse', 'factory'])\n",
    "a['cost'] = cost.flatten()\n",
    "a[:3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>warehouse</th>\n",
       "      <th>factory</th>\n",
       "      <th>cost</th>\n",
       "      <th>Var</th>\n",
       "      <th>Val</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>10</td>\n",
       "      <td>v0</td>\n",
       "      <td>28.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>10</td>\n",
       "      <td>v1</td>\n",
       "      <td>7.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>12</td>\n",
       "      <td>v6</td>\n",
       "      <td>31.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>14</td>\n",
       "      <td>v7</td>\n",
       "      <td>5.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>12</td>\n",
       "      <td>v9</td>\n",
       "      <td>22.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>12</td>\n",
       "      <td>v11</td>\n",
       "      <td>20.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    warehouse  factory  cost  Var   Val\n",
       "0           0        0    10   v0  28.0\n",
       "1           0        1    10   v1   7.0\n",
       "6           1        2    12   v6  31.0\n",
       "7           1        3    14   v7   5.0\n",
       "9           2        1    12   v9  22.0\n",
       "11          2        3    12  v11  20.0"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m2 = LpProblem()\n",
    "a['Var'] = [LpVariable('v%d'%i, lowBound=0) for i in a.index]\n",
    "m2 += lpDot(a.cost, a.Var)\n",
    "for k, v in a.groupby('warehouse'):\n",
    "    m2 += lpSum(v.Var) <= supply[k]\n",
    "for k, v in a.groupby('factory'):\n",
    "    m2 += lpSum(v.Var) >= demand[k]\n",
    "m2.solve()\n",
    "a['Val'] = a.Var.apply(value)\n",
    "a[a.Val > 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n",
      "11\n"
     ]
    }
   ],
   "source": [
    "for i in a.index:\n",
    "    print (i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "0    v0\n",
      "1    v1\n",
      "2    v2\n",
      "3    v3\n",
      "Name: Var, dtype: object\n",
      "1\n",
      "4    v4\n",
      "5    v5\n",
      "6    v6\n",
      "7    v7\n",
      "Name: Var, dtype: object\n",
      "2\n",
      "8      v8\n",
      "9      v9\n",
      "10    v10\n",
      "11    v11\n",
      "Name: Var, dtype: object\n"
     ]
    }
   ],
   "source": [
    "for k, v in a.groupby('warehouse'):\n",
    "    print (k)\n",
    "    print (v.Var)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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.5.2"
  },
  "toc": {
   "nav_menu": {
    "height": "48px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}