{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Object Oriented Convex Optimization"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "CVXPY enables an object-oriented approach to constructing optimization problems. An object-oriented approach is simpler and more flexible than the traditional method of constructing problems by embedding information in matrices.\n",
      "\n",
      "Consider the max-flow problem with `N` nodes and `E` edges. We can define the problem explicitly by constructing an `N` by `E` incidence matrix `A`. `A[i, j]` is +1 if edge `j` enters node `i`, -1 if edge `j` leaves node `i`, and 0 otherwise. The source and sink are the last two edges. The problem becomes"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# A is the incidence matrix. \n",
      "# c is a vector of edge capacities.\n",
      "flows = Variable(E-2)\n",
      "source = Variable()\n",
      "sink = Variable()\n",
      "p = Problem(Maximize(source),\n",
      "              [A*hstack([flows,source,sink]) == 0,\n",
      "               0 <= flows,\n",
      "               flows <= c])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The more natural way to frame the max-flow problem is not in terms of incidence matrices, however, but in terms of the properties of edges and nodes. We can write an ``Edge`` class to capture these properties."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Edge(object):\n",
      "    \"\"\" An undirected, capacity limited edge. \"\"\"\n",
      "    def __init__(self, capacity):\n",
      "        self.capacity = capacity\n",
      "        self.flow = Variable()\n",
      "\n",
      "    # Connects two nodes via the edge.\n",
      "    def connect(self, in_node, out_node):\n",
      "        in_node.edge_flows.append(-self.flow)\n",
      "        out_node.edge_flows.append(self.flow)\n",
      "\n",
      "    # Returns the edge's internal constraints.\n",
      "    def constraints(self):\n",
      "        return [abs(self.flow) <= self.capacity]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The `Edge` class exposes the flow into and out of the edge. The capacity constraint is stored locally in the `Edge` object. The graph structure is also stored locally, by calling `edge.connect(node1, node2)` for each edge.\n",
      "\n",
      "We also define a `Node` class:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Node(object):\n",
      "    \"\"\" A node with accumulation. \"\"\"\n",
      "    def __init__(self, accumulation=0):\n",
      "        self.accumulation = accumulation\n",
      "        self.edge_flows = []\n",
      "\n",
      "    # Returns the node's internal constraints.\n",
      "    def constraints(self):\n",
      "        return [sum(f for f in self.edge_flows) == self.accumulation]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Nodes have a target amount of flow to accumulate. Sources and sinks are Nodes with a variable as their accumulation target.\n",
      "\n",
      "Suppose `nodes` is a list of all the nodes, `edges` is a list of all the edges, and `sink` is the sink node. The problem becomes:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "constraints = []\n",
      "for obj in nodes + edges:\n",
      "    constraints += obj.constraints()\n",
      "prob = Problem(Maximize(sink.accumulation), constraints)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Note that the problem has been reframed from maximizing the flow along the source edge to maximizing the accumulation at the sink node. We could easily extend the `Edge` and `Node` class to model an electrical grid. Sink nodes would be consumers. Source nodes would be power stations, which generate electricity at a cost. A node could be both a source and a sink, which would represent energy storage facilities or a consumer who contributes to the grid. We could add energy loss along edges to more accurately model transmission lines. The entire grid construct could be embedded in a time series model.\n",
      "\n",
      "To see the object-oriented approach applied to more complex flow problems, look in the `cvxpy/examples/flows/` directory."
     ]
    }
   ],
   "metadata": {}
  }
 ]
}