Regionalization with PuLP: exact optimization model called "Tree" in Duque et al. (2011)

prm_tree_PuLP.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import libpysal as ps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Making the lattice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are generating a 3x3 lattice: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "lat_w = ps.weights.util.lat2W(nrows=3, ncols=3, rook=True, id_type=\"int\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: [3, 1],\n",
       " 1: [0, 4, 2],\n",
       " 2: [1, 5],\n",
       " 3: [0, 6, 4],\n",
       " 4: [1, 3, 7, 5],\n",
       " 5: [2, 4, 8],\n",
       " 6: [3, 7],\n",
       " 7: [4, 6, 8],\n",
       " 8: [5, 7]}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neighbor_dict = lat_w.neighbors\n",
    "neighbor_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Adding data to the lattice (_hardcoded_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 726.7,\n",
       " 1: 623.6,\n",
       " 2: 487.3,\n",
       " 3: 200.4,\n",
       " 4: 245.0,\n",
       " 5: 481.0,\n",
       " 6: 170.9,\n",
       " 7: 225.9,\n",
       " 8: 226.9}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value_list = [726.7, 623.6, 487.3, 200.4, 245.0, 481.0, 170.9, 225.9, 226.9]\n",
    "value_dict = {area: value for area, value in zip(neighbor_dict.keys(), value_list)}\n",
    "value_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Defining the optimization model from Duque et al. (2011): \"The p-Regions Problem\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from pulp import LpProblem, LpMinimize, LpVariable, \\\n",
    "                 LpInteger, lpSum, GLPK, LpStatus, \\\n",
    "                 value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "prob = LpProblem(\"Tree\", LpMinimize)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n = len(value_dict)\n",
    "p = 2  # TODO: turn this into a part of the API\n",
    "I = list(value_dict.keys())\n",
    "II = [(i, j) for i in I \n",
    "             for j in I]\n",
    "II_upper_triangle = [(i, j) for i, j in II if i < j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def dissim_measure(v1, v2):\n",
    "    \"\"\"\\\n",
    "    Returns the dissimilarity between the values v1 and\n",
    "    v2.\n",
    "    \"\"\"\n",
    "    return abs(v1 - v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {(i, j): dissim_measure(value_dict[i], value_dict[j])\n",
    "     for i, j in II}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = LpVariable.dicts(\n",
    "    \"t\",\n",
    "    ((i, j) for i, j in II),\n",
    "    lowBound=0, upBound=1, cat=LpInteger)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "x = LpVariable.dicts(\n",
    "    \"x\",\n",
    "    ((i, j) for i, j in II),\n",
    "    lowBound=0, upBound=1, cat=LpInteger)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "u = LpVariable.dicts(\n",
    "    \"u\",\n",
    "    (i for i in I),\n",
    "    lowBound=0, cat=LpInteger)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# (3) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "prob += lpSum(d[i, j] * t[i, j] for i, j in II_upper_triangle)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constraints"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (4) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "prob += lpSum(x[i, j] for i in I for j in neighbor_dict[i]) == n - p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (5) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "for i in I:\n",
    "    prob += lpSum(x[i, j] for j in neighbor_dict[i]) <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (6) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "for i in I:\n",
    "    for j in I:\n",
    "        for m in I:\n",
    "            if i != j and i != m and j != m:\n",
    "                prob += t[i, j] + t[i, m] - t[j, m] <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (7) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "for i, j in II:\n",
    "    prob += t[i, j] - t[j, i] == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "# (8) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "for i in I:\n",
    "    for j in neighbor_dict[i]:\n",
    "        prob += x[i, j] <= t[i, j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (9) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "for i in I:\n",
    "    for j in neighbor_dict[i]:\n",
    "        prob += u[i] - u[j] + (n-p) * x[i, j] \\\n",
    "                + (n-p-2) * x[j, i] <= n - p - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (10) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "for i in I:\n",
    "    prob += u[i] <= n - p\n",
    "    prob += u[i] >= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (11) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "# already in Var()-definition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (12) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "# already in Var()-definition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solve the optimization problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob.solve(GLPK(msg=0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Optimal'"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LpStatus[prob.status]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "#for v in prob.variables():\n",
    "#    print(v.name, \"=\", v.varValue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 0, 0, 1, 1, 0, 1, 1, 1])"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def find_index_of_sublist(el, lst):\n",
    "    for idx, sublst in enumerate(lst):\n",
    "        if el in sublst:\n",
    "            return idx\n",
    "    raise LookupError(\"{} not found any of the sublists of {}\".format(el, lst))\n",
    "\n",
    "# build a list of regions like [[0, 1, 2, 5], [3, 4, 6, 7, 8]]\n",
    "idx_copy = set(I)\n",
    "regions = [[] for i in range(p)]\n",
    "for i in range(p):\n",
    "    area = idx_copy.pop()\n",
    "    regions[i].append(area)\n",
    "    \n",
    "    for other_area in idx_copy:\n",
    "        if t[area, other_area].varValue == 1:\n",
    "            regions[i].append(other_area)\n",
    "    \n",
    "    idx_copy.difference_update(regions[i])\n",
    "\n",
    "# build a column with region information\n",
    "region_col = np.arange(n)\n",
    "for i in range(n):\n",
    "    region_col[i] = find_index_of_sublist(i, regions)\n",
    "    \n",
    "region_col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "area 0 is in region 0\n",
      "area 1 is in region 0\n",
      "area 2 is in region 0\n",
      "area 3 is in region 1\n",
      "area 4 is in region 1\n",
      "area 5 is in region 0\n",
      "area 6 is in region 1\n",
      "area 7 is in region 1\n",
      "area 8 is in region 1\n"
     ]
    }
   ],
   "source": [
    "for i, region in enumerate(region_col):\n",
    "    print(\"area\", i, \"is in region\", region)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1222.8"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value(prob.objective)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}