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
# 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*vstack(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.
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:
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:
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.