Object Oriented Convex Optimization
===================================

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.

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

.. code:: python

    # A is the incidence matrix. 
    # c is a vector of edge capacities.
    flows = Variable(E-2)
    source = Variable()
    sink = Variable()
    p = Problem(Maximize(source),
                  [A*hstack([flows,source,sink]) == 0,
                   0 <= flows,
                   flows <= c])

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.

.. code:: python

    class Edge(object):
        """ An undirected, capacity limited edge. """
        def __init__(self, capacity):
            self.capacity = capacity
            self.flow = Variable()
    
        # Connects two nodes via the edge.
        def connect(self, in_node, out_node):
            in_node.edge_flows.append(-self.flow)
            out_node.edge_flows.append(self.flow)
    
        # Returns the edge's internal constraints.
        def constraints(self):
            return [abs(self.flow) <= self.capacity]

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.

We also define a ``Node`` class:

.. code:: python

    class Node(object):
        """ A node with accumulation. """
        def __init__(self, accumulation=0):
            self.accumulation = accumulation
            self.edge_flows = []
    
        # Returns the node's internal constraints.
        def constraints(self):
            return [sum(f for f in self.edge_flows) == self.accumulation]

Nodes have a target amount of flow to accumulate. Sources and sinks are
Nodes with a variable as their accumulation target.

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:

.. code:: python

    constraints = []
    for obj in nodes + edges:
        constraints += obj.constraints()
    prob = Problem(Maximize(sink.accumulation), constraints)

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.

To see the object-oriented approach applied to more complex flow
problems, look in the ``cvxpy/examples/flows/`` directory.