LP-HW.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generalizations of Max-Flow\n",
    "\n",
    "The purpose of this assignment is to learn about the min-cost flow problem, a generalization of max-flow, and to familiarize yourself with implementing and solving linear programs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Min-Cost Flow\n",
    "\n",
    "Recall that a flow network with demands consists of a directed graph $G = (V, E)$, where each edge $(i,j) \\in E$ has a positive integer capacity $c_{ij}$ and each node $i \\in V$ has an integer demand $d_i$. In a *min-cost flow* problem, each edge $(i,j) \\in E$ also has a cost (or weight) $w_{ij}$. (Note that this input generalizes the input to two important problems we discussed so far: in max flow, the edge weights were not important while in shortest paths, the edge capacities were not important.) \n",
    "\n",
    "Given a flow network with capacities and costs, the goal is to find a *feasible* flow $f: E \\rightarrow R^+$ --that is, a flow satisfying edge capacity constraints and node demands-- that minimizes the total cost of the flow. Explicitly, the problem can be formulated as a linear program."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 1\n",
    "\n",
    "Answer Problem 1 in HW4-theoretical."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 2\n",
    "\n",
    "To implement your reduction from Problem 1 in HW4-theoretical, you will work with some standard benchmark instances for min-cost flow found [here](http://elib.zib.de/pub/Packages/mp-testdata/mincost/gte/index.html). The format of the data is described in the [Info](http://elib.zib.de/pub/Packages/mp-testdata/mincost/gte/info) file. You are to read in the graph from the data file in a form that can be solved using NetworkX's `min_cost_flow` function. Note that the data sometimes lists multiple edges between the same nodes, but with different costs or capacities. In forming the graph, you need to implement your reduction from the previous question and form a `DiGraph` instance, because the `min_cost_flow` function cannot handle multi-edges, even though the package offers `MultiDiGraph` objects."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "\n",
    "def create_graph(infile):\n",
    "    \"\"\"Creates a directed graph as specified by the input file. Edges are annotated with 'capacity'\n",
    "    and 'weight' attributes, and nodes are annotated with 'demand' attributes.\n",
    "    \n",
    "    Args:\n",
    "        infile: the input file using the format to specify a min-cost flow problem.\n",
    "        \n",
    "    Returns:\n",
    "        A directed graph (but not a multi-graph) with edges annotated with 'capacity' and 'weight' attributes\n",
    "        and nodes annotated with 'demand' attributes.\n",
    "    \"\"\"\n",
    "    # TODO: implement function\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following will check that your code outputs the expected min cost flow values on several test instances."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "G_40 = create_graph('gte_bad.40')\n",
    "G_6830 = create_graph('gte_bad.6830')\n",
    "G_176280 = create_graph('gte_bad.176280')\n",
    "\n",
    "print \"Correct value for _40 instance:\", nx.min_cost_flow_cost(G_40) == 52099553858\n",
    "print \"Correct value for _6830 instance:\", nx.min_cost_flow_cost(G_6830) == 299390431788\n",
    "print \"Correct value for _176280 instance:\", nx.min_cost_flow_cost(G_176280) == 510585093810"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Programming\n",
    "\n",
    "Instead of using special-purpose min-cost flow solvers, you will now formulate the problems as linear programs and use general-purpose LP solvers to find the solutions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 3\n",
    "\n",
    "Implement the following function to formulate the flow LP and return the optimal value (i.e., minimum cost over feasible flows)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import pulp\n",
    "\n",
    "def lp_flow_value(G):\n",
    "    \"\"\"Computes the value of the minimum cost flow by formulating and solving\n",
    "    the problem as an LP.\n",
    "    \n",
    "    Args:\n",
    "        G: a directed graph with edges annotated with 'capacity' and 'weight'\n",
    "            attrbutes, and nodes annotated with 'demand' attributes.\n",
    "            \n",
    "    Returns:\n",
    "        The value of the minimum cost flow.\n",
    "    \"\"\"\n",
    "    # TODO: implement function\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following will check that the LP finds the same optimal values as previously."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print \"Correct value for _40 instance:\", lp_flow_value(G_40) == 52099553858\n",
    "print \"Correct value for _6830 instance:\", lp_flow_value(G_6830) == 299390431788\n",
    "print \"Correct value for _176280 instance:\", lp_flow_value(G_176280) == 510585093810"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}