Regionalization using exact optimization model called "Flow" in Duque et al. (2011)

prm_flow.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "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": {},
   "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": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lat_w = ps.weights.util.lat2W(nrows=3, ncols=3, rook=True, id_type=\"int\")\n",
    "neighbor_dict = lat_w.neighbors\n",
    "neighbor_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Defining the data (_hardcoded_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "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": 3,
     "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": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from pyomo.environ import RangeSet, Param, Var, \\\n",
    "                          ConcreteModel, Binary, \\\n",
    "                          PositiveIntegers, \\\n",
    "                          NonNegativeIntegers, \\\n",
    "                          Objective, minimize, \\\n",
    "                          Constraint, \\\n",
    "                          Set, value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "model = ConcreteModel()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "model.n = Param(initialize=len(value_dict))  # number of areas\n",
    "model.p = Param(initialize=2)  # number of regions\n",
    "# use value(model.n) to get the value of parameter n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "model.I = RangeSet(0, model.n-1,\n",
    "                   doc=\"index for areas\")\n",
    "\n",
    "model.II = model.I * model.I\n",
    "\n",
    "II_upper_triangle = [(i, j) for i, j in model.II if i < j]\n",
    "model.II_upper_triangle = Set(initialize=II_upper_triangle,\n",
    "                              ordered=True,\n",
    "                              doc=\"2-dimensional index (i, j)\"\n",
    "                                  \"for areas where i < j\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "model.K = RangeSet(0, model.p-1,\n",
    "                   doc=\"index for regions\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 5]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def N_init(model, i):\n",
    "    \"\"\"\\\n",
    "    Returns list of areas that are adjacent to \n",
    "    area i.\n",
    "    \"\"\"\n",
    "    return neighbor_dict[i]\n",
    "\n",
    "model.N = Param(model.I, initialize=N_init)\n",
    "\n",
    "N_init(None, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def I_with_neighbors_init(model):\n",
    "    return ((i, ni) for i in model.I \n",
    "                    for ni in model.N[i]) \n",
    "\n",
    "model.I_with_neighbors = Set(dimen=2,\n",
    "                             initialize=I_with_neighbors_init,\n",
    "                             doc=\"2-dimensional index cointaining\"\n",
    "                                 \" area indices i along with \"\n",
    "                                 \"their neighborhoods N(i).\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "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": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def d_init(model, i, j):\n",
    "    \"\"\"\\\n",
    "    Returns the dissimilarity between areas i and\n",
    "    j.\n",
    "    \"\"\"\n",
    "    return dissim_measure(value_dict[i], \n",
    "                        value_dict[j])\n",
    "\n",
    "model.d = Param(model.II_upper_triangle, initialize=d_init)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "model.t = Var(model.II_upper_triangle, domain=Binary,\n",
    "              doc=\"1 if areas i and j with i < j \"\n",
    "                  \"belong to the same region.\\n\"\n",
    "                  \"0 otherwise.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.f = Var(model.II, model.K, domain=NonNegativeIntegers,\n",
    "              doc=\"The amount of flow from area i to j \"\n",
    "                  \"in region k.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "model.y = Var(model.I, model.K, domain=Binary,\n",
    "              doc=\"1 if area i is assigned to region k.\\n\"\n",
    "                  \"0 otherwise.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "model.w = Var(model.I, model.K, domain=Binary,\n",
    "              doc=\"1 if area i is chosen as a sink.\\n\"\n",
    "                  \"0 otherwise.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (20) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "def obj_rule(model):\n",
    "    return sum(model.d[i,j] * model.t[i,j]\n",
    "               for i, j in model.II_upper_triangle)\n",
    "\n",
    "model.Obj = Objective(rule=obj_rule, sense=minimize)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constraints"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (21) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "def _21(model, i):\n",
    "    return sum(model.y[i, k] for k in model.K) == 1\n",
    "\n",
    "model._21_constr = Constraint(model.I, rule=_21)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (22) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "def _22(model, i, k):\n",
    "    return model.w[i, k] <= model.y[i, k]\n",
    "\n",
    "model._22_constr = Constraint(model.I, model.K, rule=_22)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (23) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "def _23(model, k):\n",
    "    return sum(model.w[i, k] for i in model.I) == 1\n",
    "\n",
    "model._23_constr = Constraint(model.K, rule=_23)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (24) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "def _24(model, i, j, k):\n",
    "    n, p = model.n, model.p\n",
    "    return model.f[i, j, k] <= model.y[i, k] * (n-p)\n",
    "\n",
    "model._24_constr = Constraint(model.I_with_neighbors,\n",
    "                              model.K, rule=_24)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (25) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "def _25(model, i, j, k):\n",
    "    n, p = model.n, model.p\n",
    "    return model.f[i, j, k] <= model.y[j, k] * (n-p)\n",
    "\n",
    "model._25_constr = Constraint(model.I_with_neighbors,\n",
    "                              model.K, rule=_25)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (26) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "def _26(model, i, k):\n",
    "    n, p = model.n, model.p\n",
    "    lhs = sum(model.f[i, j, k] - model.f[j, i, k]\n",
    "              for j in model.N[i])\n",
    "    rhs = model.y[i, k] - (n-p) * model.w[i, k]\n",
    "    return lhs >= rhs\n",
    "\n",
    "model._26_constr = Constraint(model.I, model.K, rule=_26)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# (27) in Duque et al. (2011): \"The p-Regions Problem\"\n",
    "def _27(model, i, j, k):\n",
    "    return model.t[i, j] >= model.y[i, k] + model.y[j, k] - 1\n",
    "\n",
    "model._27_constr = Constraint(model.II_upper_triangle,\n",
    "                              model.K, rule=_27)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solve the optimization problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "from pyomo.opt import SolverFactory\n",
    "opt = SolverFactory(\"cbc\")\n",
    "results = opt.solve(model)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "area 0 is in region 1\n",
      "area 1 is in region 1\n",
      "area 2 is in region 1\n",
      "area 3 is in region 0\n",
      "area 4 is in region 0\n",
      "area 5 is in region 1\n",
      "area 6 is in region 0\n",
      "area 7 is in region 0\n",
      "area 8 is in region 0\n"
     ]
    }
   ],
   "source": [
    "for i, k in model.y.index_set():\n",
    "    if model.y[i, k].value == 1:\n",
    "        print(\"area\", i, \"is in region\", k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1222.8"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value(model.Obj)"
   ]
  },
  {
   "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
}